#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>#include <vector>#include <queue>#include <set>#include <map>#include <string>#include <math.h>#include <stdlib.h>#include <time.h>using namespace std;struct data{ int u,v; int w;} e[15000+5];bool cmp(data a, data b){ return a.w<b.w;}int n,m,bin[5000];int Find(int x){ int s; for(s=x; bin[s]>=0; s=bin[s]); while(s!=x) { int t=bin[x]; bin[x]=s; x=t; } return s;}void Union(int x1,int x2){ int f1=Find(x1),f2=Find(x2); int t=bin[f1]+bin[f2]; if(bin[f1]>bin[f2]) { bin[f1]=f2; bin[f2]=t; } else { bin[f2]=f1; bin[f1]=t; }}int main(){ int i,j,num,u,v,ans[1000+24],maxe; while(~scanf("%d%d",&n,&m)) { if(n==0) break; for(i=0; i<=n; i++) bin[i]=-1; for(i=0; i<m; i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w); sort(e,e+m,cmp); num=0; maxe=0; for(i=0; i<m; i++) { u=e[i].u; v=e[i].v; if(Find(u)!=Find(v)) { ans[num]=i; Union(u,v); num++; maxe=max(maxe,e[i].w); } if(num>=n-1) break; } printf("%dn",maxe); printf("%dn",num); for(i=0; i<num; i++) { printf("%d %dn",e[ans[i]].u,e[ans[i]].v); } } return 0;}
