#include <iostream>
#include <algorithm>
#include <fstream>
#define dmax 10000001
using namespace std;

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

struct muchie
{
    int a,b,c;
}x[dmax];

struct sol
{
    int a,b;
}v[dmax];

int n,m,t[dmax];

int main()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
        fin>>x[i].a>>x[i].b>>x[i].c;
    for(int i=0;i<m;i++)
        for(int j=i+1;j<m;j++)
        if(x[i].c>x[j].c)
        swap(x[i],x[j]);
    for(int i=1;i<=n;i++)
        t[i]=i;
    int S=0,cnt=0,k=0;
    for(int i=0;i<m;i++)
        if(t[x[i].a]!=t[x[i].b])
    {
        S+=x[i].c;
        k++;
        v[k].a=x[i].a;
        v[k].b=x[i].b;
        int a=t[x[i].a];
        int b=t[x[i].b];
        for(int j=1;j<=n;j++)
            if(t[j]==b)
            t[j]=a;
    }
    fout<<S<<endl;
    fout<<k<<endl;
    for(int i=1;i<=k;i++)
        fout<<v[i].a<<" "<<v[i].b<<endl;
    return 0;
}