受何老板之托，嵩嵩在美国为何老板采购的若干吨货物。这批货物已通过水路运送到了我国某沿海城市，现在需要通过公路将这些货物运送到何老板家。嵩嵩的地图上有N(2 <= N <= 200) 座城市，编号1到N，嵩嵩在1号城市，何老板的家在N号城市。这N座城市间有P(1 <= P <= 40,000) 条双向通行的道路相连，每条道路长度不超过1,000,000。两座城市间可能有多条道路相连。
嵩嵩雇了T(1 <= T <= 200)辆卡车运送这批货物。为了避免被人发现或引起别人的注意，嵩嵩安排这T辆车选择不同的道路行驶，也就是同一条道路不会被走两次。
请帮助嵩嵩安排这T辆车的线路，使得走过的最长的一条道路尽可能短。
嵩嵩向你保证在不走重复道路的情况下，一定能够把T车货物运到目的地。
注意：题目中描述的“道路”相当于图论中的“边”。

第一行包括三个空格间隔的整数N,P,T。
接下来P行，每行有三个空格间隔的整数A,B,C。表示城市A、B间有条长度为C的道路。

一整数，表示经过的最长道路最短可能的长度。

样例说明：
两次行走的线路分别是1 - 2 - 3 - 7和1 - 6 - 7. 其中最长一条道路的长度是5。
也就是说不可能找到两条可行的线路，使得其中最长的一条道路的长度比5更小。

番外篇：NKOJ3000