#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

vector<pair<int,pair<int,int> > > v;
int s[200010];
vector<int> nod;
int n,m,i,a,b,j,cost,nr,c,aux;

void afiseaza()
{
    for(i=0;i<m;++i)
    fout<<v[i].first<<" "<<v[i].second.first<<" "<<v[i].second.second<<'\n';
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        v.push_back(make_pair(c,make_pair(a,b)));
    }
    for(i=1;i<=n;++i)
    s[i]=i;
    sort(v.begin(),v.end());
    //afiseaza();
    for(i=0;i<m;++i)
    {
        a=v[i].second.first; b=v[i].second.second;
        if(s[a]!=s[b])
        {
            aux=s[a];
            for(j=1;j<=n;++j)
            if(s[j]==aux) s[j]=s[b];
            cost+=v[i].first;
            nod.push_back(i);
            nr++;
        }
        if(nr==n-1)
        break;
    }
    fout<<cost<<'\n'<<n-1<<'\n';
    for(i=1;i<n;++i)
    fout<<v[nod[i-1]].second.first<<" "<<v[nod[i-1]].second.second<<'\n';

    return 0;
}