#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int n,m;
struct nod{
    int x;
    int y;
    int c;
}v[200003];
bool comp(struct nod a,struct nod b)
{
    return a.c<b.c;
}
struct solutie
{
    int x0;
    int y0;
}sol[200003];
int mul[200003];
int main()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>v[i].x>>v[i].y>>v[i].c;
    sort(v+1,v+m+1,comp);
    int nr=0;
    for(int i=1;i<=n;i++)
        mul[i]=i;
    int contor=1;
    int var;
    int total=0;
    while(nr<n)
    {
        if(mul[v[contor].x]!=mul[v[contor].y])
        {
            total+=v[contor].c;
            nr++;
            sol[nr].x0=v[contor].x;
            sol[nr].y0=v[contor].y;
            var=mul[v[contor].y];
            for(int j=1;j<=n;j++)
                if(mul[j]==var)
                    mul[j]=mul[v[contor].x];
        }
        contor++;
    }
    g<<total<<"\n";
    g<<n-1<<"\n";
    for(int i=1;i<=n-1;i++)
        g<<sol[i].x0<<" "<<sol[i].y0<<"\n";
    return 0;
}