#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
struct muchie{int x,y,cost;};

bool compar (muchie m1, muchie m2)
{
    return m1.cost < m2.cost;
}
int main()
{
    fstream f("apm.in",ios::in);
    fstream out("apm.out",ios::out);
    vector<muchie> u;
    vector<muchie> rez;
    int n,m,arb[200001],i,ma,costot=0,j,arbtemp,x,y,cost;

    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>cost;
        muchie m;
        m.x=x;
        m.y=y;
        m.cost=cost;

        u.push_back(m);
    }
    sort(u.begin(), u.end(), compar);

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

    ma=0;
    i=0;

    while(ma<n-1)
    {
        if(arb[u[i].x]!=arb[u[i].y])
        {
            costot+=u[i].cost;

            muchie mu;
            mu.x=u[i].x;
            mu.y=u[i].y;

            rez.push_back(mu);

            ma++;
            arbtemp=arb[u[i].y];
            for(j=1;j<=n;j++)
                if(arb[j]==arbtemp)
                    arb[j]=arb[u[i].x];
        }
        i++;
    }

    out<<costot<<endl<<n-1<<endl;

    for(i=0;i<n-1;i++)
        out<<rez[i].x<<" "<<rez[i].y<<endl;
}