1 #include
     
       2 using namespace std; 3  4 struct Vertex{ 5     int start, end; 6     int weight; 7 }; 8 Vertex arr[10000]; 9 int par[10000];10 int n, m;11 int find(int n){12     while(par[n] != n){13         n = par[n];14     }15     return n;16 }17 void merge(int n1, int n2){18     while(par[n1] != n1){19         n1 = par[n1];20         par[n1] = n2;21     }22     par[n1] = n2;23 }24 bool cmp(Vertex v1, Vertex v2){25     return v1.weight < v2.weight;26 }27 28 void init(){                       29     for(int i = 0; i <= n; i++)par[i] = i;30 }31 32 long long func(int k){33     init();34     int weight_max = 0;35     int i = 0;36     bool fail = false;37     int kk = k;38     while(i < n-1){39         if(k >= m){40             fail = true;41             break;42         }43         Vertex tmp = arr[k++];44         int n1 = find(tmp.start);45         int n2 = find(tmp.end);46         if(n1 == n2){47             continue;48         }49         else{50             if(i == n-2){51                 weight_max = tmp.weight;52             }53             if(n1 > n2)swap(n1, n2);54             merge(n2, n1);55             i++;56         }57     }58     59     if(fail) return -1;60     else return weight_max - arr[kk].weight;61 }62 63 int main(){64     while(scanf("%d%d", &n, &m) != EOF && (n != 0 || m != 0)){65         init();66         for(int i = 0; i < m; i++){67             scanf("%d%d%d", &arr[i].start, &arr[i].end, &arr[i].weight);68         }69         int MIN = 100000000;70         sort(arr, arr+m, cmp);71         for(int i = 0; i < m; i++){72             int tmp = func(i);73             if(tmp != -1)MIN = min(MIN, tmp);74         }75         if(MIN == 100000000){76             printf("-1\n");77         }78         else{79             printf("%d\n", MIN);80         }81     }82 }