#include <fstream>
#include <algorithm>

using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int T[101000], Rang[101000];

struct elem
{
    int s,d,c;
}x[400001],af[200001];

int pret(elem a, elem b)
{
    return a.c<b.c;
}

int Radacina(int k)
{
    if(T[k] == 0)
        return k;
    else
    {
        int x = Radacina(T[k]);
        T[k] = x;
        return x;
    }
}

void Unire(int k, int p)
{
    int rk = Radacina(k), rp = Radacina(p);
    if(rk != rp)
    {
        if(Rang[rk] > Rang[rp])
            T[rp] = rk;
        else
        {
            T[rk] = rp;
            if(Rang[rk] == Rang[rp])
                Rang[rp] ++;
        }
    }
}

int main()
{
    int n, m, t[200001], as, ad, cm=0, z=0;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i].s>>x[i].d>>x[i].c;
    }
    sort(x+1,x+m+1,pret);
    for(int i=1;i<=n;i++) t[i]=i;
    for(int i=1;i<=m;i++)
    {
        if(Radacina(x[i].s)!=Radacina(x[i].d))
        {
            Unire(x[i].s, x[i].d);
            cm+=x[i].c;
            af[++z].s=x[i].d;
            af[z].d=x[i].s;
        }
    }
    cout<<cm<<'\n'<<z<<'\n';
    for(int i=1;i<=z;i++) cout<<af[i].s<<' '<<af[i].d<<'\n';
    return 0;
}