排水系统
时间限制: 1 s
内存限制: 128 MB
提交：6
正确：0
分值：100
题目描述
沉没的亚特兰蒂斯上曾经有着高度发达的人类文明。亚特兰蒂斯文明的都城叫做波赛多尼亚，因为那里有供奉着海神波赛冬的宏伟的神殿，波赛多尼亚城里有着复杂而有效的排水系统，为城里的居民提供生活上的便利。准确来说。城里共有M条排水管道，连接着N座建筑。每条排水管道连接两座不同的建筑。水可以在排水管道内任意流动。两座建筑之间最多有一条排水管道直接相连。在这个排水网上有两个建筑非常重要：海神波塞冬的神殿，以及一个唯一的出海口。
城里的居民非常担心神殿的排水出现问题，因为那会触怒他们最尊敬的神明，他们决定修理他们的排水管道，但是却凑不到足够的材料，于是他们决定只加固这么一条管道，若这条管道完全堵塞，其他水管正常工作的时候，水从神殿流到出海口的最短距离最长。输入数据保证任意一条管道堵塞时依然有从神殿到出海口的排水通道。
输入
输入文件的第一行包含两个正整数N（3≤N≤10000），M（1≤M≤50000）。
以下M行，每行包含三个正整数u、v、L（0≤u,v<N，u≠v，1≤L≤1000），表示编号为u和v的两座建筑由一条长度L的排水管道直接连接。建筑物是从0开始编号的，神殿的编号为0，出海口的编号为1。
输入文件只包含一组数据。
输出
输出一个正整数，表示被维修的这条管道堵塞的时候水从神殿流到出海口的最短距离。
样例
样例输入:
6 8
0 2 10
0 4 12
2 3 6
4 5 3
3 4 12
2 5 4
3 1 5
5 1 24
样例输出:
38