1306: 盗窃团伙II
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 846 Solved: 216
[Submit] [Status] [Web Board] [Creator:]
Description
听说PIPI家又有新产品了，盗窃团伙麓石开的鸡腿和xiefang开始计划着要去PIPI家偷产品了。要是偷到了，他们就可以把PIPI家的产品理不直气也壮的高价售出了！！！
CSU的地下有二战时构建的地下交通网络，交通网络中有n个枢纽，m条隧道，每个隧道都连接了两个交通枢纽。麓石开团伙在 1 号枢纽，而PIPI家的产品中心刚好位于n号枢纽，现在他们准备从地下隧道直通PIPI家的产品中心。但是这些隧道已经年久失修，需要翻新一遍才能够安全通过。现在麓石开想请若干家施工公司将其中的一些隧道翻新，使得他们能够从 1 号枢纽走到 n 号枢纽。这些施工公司能够同时开工翻新隧道，但是每一家公司都只能翻新一条隧道。 （两个枢纽之间可能有多条隧道）
麓石开只想着尽可能早一点的偷到PIPI家的新产品，请问至少需要多少天，他们才能够修通隧道，进入PIPI家的产品中心偷产品？？
CSU的地下有二战时构建的地下交通网络，交通网络中有n个枢纽，m条隧道，每个隧道都连接了两个交通枢纽。麓石开团伙在 1 号枢纽，而PIPI家的产品中心刚好位于n号枢纽，现在他们准备从地下隧道直通PIPI家的产品中心。但是这些隧道已经年久失修，需要翻新一遍才能够安全通过。现在麓石开想请若干家施工公司将其中的一些隧道翻新，使得他们能够从 1 号枢纽走到 n 号枢纽。这些施工公司能够同时开工翻新隧道，但是每一家公司都只能翻新一条隧道。 （两个枢纽之间可能有多条隧道）
麓石开只想着尽可能早一点的偷到PIPI家的新产品，请问至少需要多少天，他们才能够修通隧道，进入PIPI家的产品中心偷产品？？
Input
输入的第一行包含两个整数n, m，用一个空格分隔，分别表示交通枢纽的数量和候选隧道的数量 (n<=1e5 , m<=2e5)。
第2行到第m+1行，每行包含三个整数a, b, c，表示枢纽a和枢纽b之间可以修建一条隧道，需要的时间为c天 (1<=a,b<=n , 0<c<=1e5)。
第2行到第m+1行，每行包含三个整数a, b, c，表示枢纽a和枢纽b之间可以修建一条隧道，需要的时间为c天 (1<=a,b<=n , 0<c<=1e5)。
Output
输出盗窃团伙至少需要多少天才能偷到PIPI家的产品？若PIPI足够幸运，让他们没有办法偷到产品，则输出"How lucky!"
Sample Input
6 6
1 2 4
2 3 4
3 6 7
1 4 2
4 5 5
5 6 6
Sample Output
6
HINT
然鹅PIPI并没有 How lucky 的时候 ，o(╥﹏╥)o