#include <bits/stdc++.h>

using namespace std;

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

int n,m,x,y,c,i,radacina[200005],noduri,cost,apm[200005][2];
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;
    for (i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        p.push(make_pair(-c,make_pair(x,y)));
    }
    for (i=1;i<=n;i++)
        radacina[i]=i;
    while (noduri<n-1)
    {
        auto t=p.top();
        p.pop();
        if (rad(t.second.first)!=rad(t.second.second))
        {
            cost-=t.first;
            noduri++;
            radacina[rad(t.second.first)]=rad(t.second.second);
            apm[noduri][0]=t.second.first;
            apm[noduri][1]=t.second.second;
        }
    }
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for (i=1;i<=n-1;i++)
        fout<<apm[i][0]<<" "<<apm[i][1]<<'\n';
    return 0;
}