2569: 运送货物

有N个城市(编号1−N)，城市之间有M条无向道路，每条路有一个最大载重量的限制。现在有一批货物要从城市1运到城市N，机智的HS会从城市1到城市N的路之间找一条路使能运送的货物尽量多。

第一行是一个整数T(T≤50)，表示有T组数据。
每组数据第一行有两个整数N(2≤N≤1000),M(0≤M≤100000)
接下来M行，每行三个整数u(1≤u≤N),v(1≤v≤N),w(0≤w≤1000000000)，表示城市u到城市v之间有一条载重量为w的路。

输出1−N路径上能载重最多货物的路的载重量是多少，如果城市1不能到达城市N，输出0。

1
3 3
1 2 3
1 3 4
2 3 5

4