Bessie 来到一个小农场，有时她想回老家看看她的一位好友。她不想太早地回到老家，因为她喜欢途中的美丽风景。她决定选择次短路径，而不是最短路径。 农村有 R (1 <= R <= 100,000) 条双向的路，每条路连接 N (1 <= N <= 5000) 个结点中的两个。结点的编号是 1..N。Bessie 从结点 1出发，她的朋友（目的地）在结点 N。 次短路径可以使用最短路径上的路，而且允许退回，即到达一个结点超过一次。次短路径是一种长度大于最短路径的路径(如果存在两条或多条最短路径存在，次短路径就是比它们长，且不比其他任何的路径长的路径）。

* Line 1: 两个用空格分隔的整数 N 和 R * Lines 2..R+1: 每行包含三个用空格分隔的整数： A, B, 和 D表示有一条路连接 结点A和B，长度为D (1 <= D <= 5000)。

* Line 1: 结点 1 到结点 N的次短路径长度。

4 4
1 2 100
2 4 200
2 3 250
3 4 100

450