#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct muchie
{
    int x,y,c;
} v[101];

int n, m, comp[101];

bool conditie(muchie i, muchie j)
{
    return i.c<j.c;
}

int main()
{
    ifstream f("apm.in");
    ofstream g("apm.out");

    vector <pair<int,int>> muchii;
    int i,j,k,cost,s=0,x,y;
    f>>n>>m;
    k=0;
    while(f>>i>>j>>cost)
    {
        v[k].x=i;
        v[k].y=j;
        v[k].c=cost;
        k++;
    }
    sort(v,v+m,conditie);

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

    int cmpx,cmpy;
    for(i=0; i<m; i++)
    {
        x=v[i].x;
        y=v[i].y;
        if(comp[x] != comp[y])
        {
            muchii.push_back(make_pair(x,y));
            s+=v[i].c;
            cmpx=comp[x];
            cmpy=comp[y];
            for(j=1; j<=n; j++)
                if(comp[j]==cmpy)
                    comp[j]=cmpx;
        }
    }

    g<<s<<endl;
    g<<n-1<<endl;
    for(i=0;i<muchii.size();i++)
        g<<muchii[i].first<<' '<<muchii[i].second<<endl;

    return 0;
}