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

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

int n,m,i,a,b,c;
vector<pair<int,pair<int,int > > > v;
vector<pair<int,int> > sol;
int s[200010];
int nr,auxa,auxb;
int S;

int Find(int x)
{
    if(s[x]==x)
    return x;
    else
    return s[x]=Find(s[x]);
}

void connect(int a,int b)
{
    s[a]=b;
    sol.push_back(make_pair(a,b));
}

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)));
    }
    sort(v.begin(),v.end());

    for(i=1;i<=n;++i)
    s[i]=i;

    nr=0;
    for(i=0;i<m;++i)
    {
        a=v[i].second.first;
        b=v[i].second.second;

        auxa=Find(a); //disjoint
        auxb=Find(b); //disjoint
        if(auxa!=auxb)
        {
            nr++;
            S+=v[i].first;
            connect(a,b);//disjoint

            if(nr==n-1)
            break;
        }
    }

    fout<<S<<'\n'<<n-1<<'\n';
    for(i=0;i<n-1;++i)
    fout<<sol[i].first<<" "<<sol[i].second<<'\n';

    return 0;
}