#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
priority_queue<  pair<int,pair<int,int> >  ,vector< pair<int,pair<int,int> > >, greater< pair<int,pair<int,int> > > >qq;
pair<int,int> kk[105];
 pair<int,pair<int,int> > cc;
int n,m,a,b,c,viz[105],maxx,minn;
long long cost;
int main()
{
    fin>>n>>m;
    for(;m;m--)
    {
        fin>>a>>b>>c;
        qq.push({c,{a,b} });
    }
    for(int i=1;i<=n;i++)
        viz[i]=i;
    for(int i=1;i<n;i++)
    {
        cc=qq.top();
        qq.pop();
        while(viz[cc.second.first]==viz[cc.second.second])
        {
            cc=qq.top();
            qq.pop();
        }
        kk[i].first=cc.second.first;
        kk[i].second=cc.second.second;
        cost+=cc.first;
        minn=min(viz[cc.second.second],viz[cc.second.first]);
        maxx=max(viz[cc.second.second],viz[cc.second.first]);
        viz[cc.second.first]=minn;
        viz[cc.second.second]=minn;
        for(int k=1;k<=n;k++)
            if(viz[k]==maxx)
                viz[k]=minn;

    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(int i=1;i<n;i++)
        fout<<kk[i].first<<" "<<kk[i].second<<'\n';
    return 0;
}