Problem1306--盗窃团伙II

1306: 盗窃团伙II

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 144  Solved: 42
[Submit] [Status] [Web Board] [Creator:]

Description

听说PIPI家又有新产品了,盗窃团伙麓石开鸡腿xiefang开始计划着要去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)。

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

Source/Category