2171: block

培训基地在你的帮助下已经确定下来。市里下发的学校连接图上的路径都是以"就近原则"来构造的，以方便学生到达最近的培训基地。
    可是就有这样的人，他不愿意"就近"。这不，NFLS就有一位"怪才"，他希望欣赏从1号学校去N号学校途中的美丽风景。怪就怪在他不愿意走1号学校到N号学校的最短的路，而是走比最短的路长一点的路（次短路径）。
    次短路径可以使用最短路径上的路，而且允许退回，即到达一个结点超过一次。次短路径是一种长度大于最短路径的路径(如果存在两条或多条最短路径存在，次短路径就是比它们长，且不比其他任何的路径长的路径）。
    所有学校之间有R(1 <= R <= 100,000)条双向的路，每条路连接N(1 <= N <= 5000)所学校中的两所，学校的编号是从1到N。

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

  一行： 结点 1 到结点 N的次短路径长度。

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

450