#include<iostream>
#include<fstream>
#include<algorithm>
#define Nmax 200005
#define Mmax 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int i,j,n,m,v[Nmax],cost;
struct arbore{int x,y,c;}a[Mmax],t[Nmax];
int cmp(arbore a,arbore b)
{
    return (a.c<b.c);
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
        {
            f>>a[i].x>>a[i].y>>a[i].c;
        }
    v[a[1].x]=1;    v[a[1].y]=1;    cost=a[i].c;    t[1].x=a[1].x;  t[1].y=a[1].y;
    sort(a+1,a+m+1,cmp);
    for(i=1;i<=n-1;i++)
    {
        j=1;
        while(v[a[j].x]==v[a[j].y]) j++;
        if(v[a[j].x]==1)
            v[a[j].y]=1;
        else
            v[a[j].x]=1;
        cost=a[j].c+1;
        t[i+1].x=a[j].x;    t[i+1].y=a[j].y;
    }
    g<<cost<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=n;i++)
        g<<t[i].x<<" "<<t[i].y<<'\n';
    return 0;
}