#include<bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
vector< pair <int, int> >nod[9000];
int tata[9000],cost[9000],s=0,n,m,i,j,alp,c1[9000],c2[9000];
int main()
{
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        nod[c].push_back(make_pair(x,y));
    }
    for(i=1;i<=n;i++)tata[i]=i;
    i=0;
    for(j=1;j<=9000;j++){
            while(!nod[j].empty())
            {
                if(tata[nod[j].back().first]!=tata[nod[j].back().second]){
                s=s+j;
                int aux=tata[nod[j].back().first];
                for(int o=1;o<=n;o++){
                 if(tata[o]==aux)
                tata[o]=tata[nod[j].back().second];
                }
                c1[i]=nod[j].back().first;
                c2[i]=nod[j].back().second;
                nod[j].pop_back();
                i++;
                if(i>=n-1)break;
                }
                else
                {
                    if(i>=n-1)break;
                    nod[j].pop_back();
                }
            }
            if(i>=n-1)break;
    }
            fout<<s<<endl;
    for(i=0;i<n-1;i++)fout<<c1[i]<<" "<<c2[i]<<endl;
}