#include <bits/stdc++.h>

using namespace std;

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