最近湯華鎮的雪下得非常的大 道路常常會被白雪蓋住而無法使用
這個時候居民(還有可憐的你)就必須要出來辛苦的鏟雪
不過這幾天情況越來越糟糕
整個小鎮的人力已經不足以維護所有的道路了
於是鎮長決定保留最少條的路可以讓大家彼此之間都有路徑相通就可以了
但是他希望能夠讓兩兩之間的最長路徑最短
你，身為遊戲的主角(?)，能夠幫助大家找出最佳的保留方式嗎？
※ 在這裡只需要印出任意兩件建築物中最遠的距離即可
第一行有一個正整數 T 代表有幾組測試資料
每組測資的第一行有兩個整數 N、M (2≤N≤500, N-1≤M≤2500)
分別代表湯華鎮上有幾間建築物和幾條道路
接下來 M 行每行有三個整數 u、v、w
表示 u 跟 v 之間有一條長度為 w 的道路相連
(1≤u,v≤N, 1≤w≤50000)
道路都是雙向的，兩棟建築物之間最多只會有一條道路連接，而且不會有道路的兩端都是連到同一棟建築物。
輸出最佳保留方式中兩兩之間最長的距離
2 6 6 1 2 1 2 3 5 3 6 3 3 4 7 4 5 2 5 6 6 2 1 1 2 9
15 9
Migrated from old NTUJ.
| No. | Testdata Range | Score |
|---|