输入的第一行有两个整数，分别代表图的点数 $n$ 和边数 $m$。

第 $2$ 到第 $(m+1)$ 行，每行 $3$ 个整数 $u,v,w$，代表存在一条从 $u$ 到 $v$ 边权为 $w$ 的边。

输出一行一个整数，代表 $1$ 到 $n$ 的最长路。

若 $1$ 与 $n$ 不联通，请输出 $-1$。

数据规模与约定

• 
  对于 $20\%$的数据，$n\le 100$，$m\le 10^3$。
  


• 
  对于 $40\%$ 的数据，$n\le 10^3$，$m\le 1$。
  


• 
  对于 $100\%$ 的数据，$1\le n\le 1500$，$1\le m\le 5\times 10^4$，1≤u,v≤n,$-10^5\le w\le 10^5$。