#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

struct w{unsigned long x,y; short c;};
bool way(w i, w j) {return(i.c<j.c);}
unsigned long n,m,i,k;
w v[400000],u[200000];
bool sem,viz[200000];
long costtotal;

void citire()
{
    f>>n>>m;
    for (i=1;i<=m;i++) f>>v[i].x>>v[i].y>>v[i].c;
}

int main()
{
    citire();
    sort(v+1,v+m+1,way);
    k=1;
    viz[v[1].x]=1;
    viz[v[1].y]=1;
    costtotal=v[1].c;
    u[1].x=v[1].x;
    u[1].y=v[1].y;
    do
    {
        sem=0;
        for (i=1;i<=m;i++)
        {
            if (viz[v[i].x]!=viz[v[i].y])
            {
                k++;
                viz[v[i].x]=1;
                viz[v[i].y]=1;
                costtotal+=v[i].c;
                sem=1;
                u[k].x=v[i].x;
                u[k].y=v[i].y;
            }
            if (sem) break;
        }
    }while(k<n-1);
    g<<costtotal<<endl<<n-1<<endl;
    for (i=1;i<n;i++) g<<u[i].x<<" "<<u[i].y<<endl;
    g.close();
    return 0;
}