問題描述 Description

小明是一個快樂的農場主，他有N$N$個農場，編號從1$1$到N$N$，因為每個農場距離很遠，現在他想修一些路使得任意兩個農場都有道路能夠到達。設計師給出了N$N$個農場由M$M$條公路相連的設計圖，小明希望修的道路盡可能的少并且在修完的所有道路中最長的路程和最短的路程之間差值最小。

輸入 Input

第一行給出N,M$N,M$。 接下來M$M$行，每一行包含三個整數：u,v,c$u,v,c$,表示農場u$u$和農場v$v$之間有一條路可以互達，路程c$c$。 保證無重邊，無自環，0<c≤107$0/lt c/le 10^7$。

輸出 Output

輸出一行包括一個整數，表示在修完的所有道路中最長的路程和最短的路程之間的最小差值。如果不能實現任意兩個農場都有道路能夠互達，輸出?1$-1$。

樣例輸入 Sample Input

3 3 1 2 1 1 3 2 2 3 3

樣例輸出 Sample Output

1

限制 Limits

對于30%$30/%$的數據有2≤N≤20$2/le N/le 20$ 對于60%$60/%$的數據有2≤N≤50$2/le N/le 50$ 對于100%$100/%$的數據有2≤N≤100,0≤M≤N×(N?1)2$2/le N/le 100,0/le M/le /frac{N/times (N-1)}{2}$

黑歷史題，詳見UVa1395 苗條的生成樹。 因為當最小邊確定時，最小生成樹唯一確定，所以枚舉所有最小邊，生成最小生成樹，然后比較答案，選擇最優解。 時間O(mlogm+mn)$O(mlogm+mn)$ 我也不知道為什么要開5s$5s$。 Code