#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
int m,n,S,i;
int x,y,c;
int Cda[200000],Tna[200000];
int a[i];
int F[200000][2];
struct muchie{int b,c;muchie *n;} *a[200000],*p;


void gs()
{

}
void dbt()
{

}
void gn(int i)
{
    while(a[i]!=NULL)
    {
        if(Cda[a[i].b]>Cda[a[i].c])
        {
            Cda[a[i].b]=Cda[a[i].c];
            Tna[a[i].b]=i;
        }
        a[i]=a[i]->n;
    }
}
int main()
{
    f>>n>>m;
    for(int i=0;i<m;++i){
            f>>x>>y>>c;
            p=new muchie;
            p->b=y;p->c=c;
            p->n=a[x];
            a[x]=p;
            p=new muchie;
            p->b=x;p->c=c;
            p->n=a[y];
            a[y]=p;
    }
    for(int i=1;i<=n;++i)v[i]=INF;
    v[1]=0;
    gn(1);
    m=1;
    while(m!=n)
    {
        gs();


        ++m;
    }
    /*for(i=1;i<m;++i)
    {
        if(v[a[i].a]!=v[a[i].b])
    {
        v[a[i].a]=v[a[i].b]=1;
        S+=a[i].c;
        i=0;
    }
    }*/
    g<<S<<'\n'<<n-1<<'\n';
    for(int i=1;i<n;++i)g<<F[i][0]<<' '<<F[i][1]<<'\n';
}