include <bits/stdc++.h>

using namespace std;

struct edge{

long long u,v,w;

}e[2000005]; long long n,m,cnt=0,sum=0,f[2000005],ma=0; long long a1[20005],b1[20005]; int ji=0; bool cmp(edge x,edge y){

return x.w<y.w;

} int find(int x) {

if (f[x] == x) {
    return x;
}

int y = find(f[x]);
f[x] = y;
return y;

} int k(){

long long sum=0;
for(int i=1;i<=m;i++){
	int u,v,w;
	u=e[i].u;
	v=e[i].v;
	w=e[i].w;
	if(find(u)==find(v)){
		continue;
	}else{
		int a=find(u);
		int b=find(v);
		f[a]=b;
		cnt++;
		a1[ji]=u;
		b1[ji]=v;
		ji++;
		if(ma<w){
			ma=w;
		} 
	}
	
}
return ma;

} int main() {

cin>>n>>m;
for(int i=1;i<=m;i++){
	cin>>e[i].u>>e[i].v>>e[i].w;
}
for(int i=1;i<=n;i++){
	f[i]=i;
}
sort(e+1,e+m+1,cmp);
int p=k();
cout<<p<<endl;
cout<<n<<endl;
for(int i=0;i<ji;i++){
	cout<<a1[i]<<" "<<b1[i]<<endl;
}
return 0;

}