#include <iostream>  
#include <queue>  
using namespace std;  
#define MAXM 15010  
#define MAXV 1010  
  
typedef struct{  
    int s,t,w;  
}Edge;  
  
int n,m,set[MAXV];  
Edge edge[MAXM];  
  
int find(int x){  
    int rt;  
    if(set[x]!=x){  
        rt=find(set[x]);  
        set[x]=rt;  
        return set[x];  
    }else return x;  
}  
  
bool Union(int a,int b){  
    int fa,fb;  
    fa=find(a);  
    fb=find(b);  
    if(fa==fb) return 0;  
    set[fa]=fb;  
    return 1;  
}  
  
void kruskal(){  
    queue <int>q;  
    int i,ans=-1,cnt=0;  
    for(i=1;i<=m;i++){  
        if(Union(edge[i].s,edge[i].t)){  
            if(ans<edge[i].w) ans=edge[i].w;  
            q.push(i);  
            if((++cnt)==(n-1)) break;   //已经找到n-1条边了  
        }  
    }  
    printf("%d\n",ans);  
    printf("%d\n",q.size());  
    while(!q.empty()){  
        i=q.front();q.pop();  
        printf("%d %d\n",edge[i].s,edge[i].t);  
    }  
}  
  
int cmp(const void * a,const void *b){  
    return (*(Edge*)a).w-(*(Edge*)b).w;  
}  
  
int main(){  
    int i;  
    while(~scanf("%d%d",&n,&m)){  
        for(i=0;i<=n;i++) set[i]=i;  
        for(i=1;i<=m;i++){  
            scanf("%d%d%d",&edge[i].s,&edge[i].t,&edge[i].w);  
        }  
        qsort(edge+1,m,sizeof(edge[0]),cmp);  
        kruskal();  
    }  
    return 0;  
}