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

using namespace std;

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

int m, n, root[200005], sum, X[200005], Y[200005];

struct Much
{
    int x, y, cost;
};

Much M[400005];

bool cmp(Much a, Much b)
{
    return a.cost<b.cost;
}

int _find(int a)
{
    int t, x, i;
    t=a;
    while(root[t]!=t)
    {
        t=root[t];
    }
    i=a;
    while(i!=t)
    {
        x=root[i];
        root[i]=t;
        i=x;
    }
    return t;
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>M[i].x>>M[i].y>>M[i].cost;
    }
    sort(M+1,M+m+1,cmp);
    for(int i=1;i<=n;i++)
        root[i]=i;
    int nrm=0;
    for(int i=1;i<=m;i++)
    {
        int tx=_find(M[i].x);
        int ty=_find(M[i].y);
        if(tx!=ty)
        {
            root[ty]=tx;
            sum+=M[i].cost;
            nrm++;
            X[nrm]=M[i].x;
            Y[nrm]=M[i].y;
            if(nrm>=n-1)
                i=m+1;
        }
    }
    fout<<sum<<'\n'<<nrm<<'\n';
    for(int i=1;i<=nrm;i++)
    {
        fout<<X[i]<<" "<<Y[i]<<'\n';
    }
    return 0;
}