#include <iostream>
#include <algorithm>

using namespace std;


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

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

int main()
{
    int n, m, t[1001], 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(t[x[i].s]!=t[x[i].d])
        {
            as=t[x[i].s];
            ad=t[x[i].d];
            for(int j=1;j<=n;j++) if(t[j]==ad) t[j]=as;
            cm+=x[i].c;
            af[++z].s=x[i].s;
            af[z].d=x[i].d;
        }
    }
    cout<<cm<<'\n'<<z<<'\n';
    for(int i=1;i<=z;i++) cout<<af[i].s<<' '<<af[i].d<<'\n';
    return 0;
}