#include <bits/stdc++.h>

using namespace std;

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

int n,m,x,y,c,radacina[200001],united,apm[200001][2],cost;
priority_queue<pair<int,pair<int,int> > > p;

int rad(int nod)
{
    if (radacina[nod]==nod)
        return nod;
    else radacina[nod]=rad(radacina[nod]);
    return radacina[nod];
}

int main()
{
    fin>>n>>m;
    united=n-1;
    for (int i=1;i<=n;i++)
        radacina[i]=i;
    for (int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        p.push(make_pair(-c, make_pair(x,y)));
    }
    while (united>0)
    {
        auto t=p.top();
        p.pop();
        if (rad(t.second.first)!=rad(t.second.second))
        {
            cost-=t.first;
            radacina[rad(t.second.first)]=rad(t.second.second);
            united--;
            apm[united][0]=t.second.first;
            apm[united][1]=t.second.second;
        }
    }
    fout<<cost<<endl;
    fout<<n-1<<endl;
    for (int i=1;i<=n-1;i++)
        fout<<apm[i][0]<<" "<<apm[i][1]<<endl;
    return 0;
}