Source : 信息学奥赛一本通训练指导教程
Description

  罗老师被邀请参加一个舞会,是在城市 nn,而罗老师当前所处的城市为 11,附近还有很多城市 2n12\sim n-1,有些城市之间没有直接相连的路,有些城市之间有直接相连的路,这些路都是双向的,当然也可能有多条。
  现在给出直接相邻城市的路长度,罗老师想知道从城市 11 到城市 nn,最短多少距离。

Input

  输入 nnmm,表示 nn 个城市和 mm 条路;
  接下来 mm 行,每行 a b ca\ b\ c, 表示城市 aa 与城市 bb 有长度为 cc 的路。

Output

  输出 11nn 的最短路。如果 11 到达不了 nn,就输出-1。

Sample Input
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output
90