#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct Muchie
{
    int x,y,c;
} v[400005];
int t[200005],h[200005],n,m,mu[400005],nr;
long long ct;
int compar(Muchie a,Muchie b)
{
    return a.c<b.c;
}
int muchie(int x,int y)
{
    int r1=x,r2=y,x1,y1,c;
    while(t[r1]!=r1) r1=t[r1];
    while(t[r2]!=r2) r2=t[r2];
    if(r1==r2) return 0;
    while(t[x]!=r1)
    {
        x1=t[x];
        t[x]=r1;
        x=x1;
    }
    while(t[y]!=r2)
    {
        y1=t[y];
        t[y]=r2;
        y=y1;
    }
    if(h[r1]>h[r2])
    {
        t[r2]=r1;
        c=r1;
    }
    else {t[r1]=r2;c=r2;}
    if(h[r1]==h[r2]) h[c]++;
    return 1;
}
void kruskal()
{
    int k=0,i=1;
    while(k<n-1)
    {
        if(muchie(v[i].x,v[i].y))
        {
            ct+=v[i].c;
            k++;
            mu[k]=i;
        }
        i++;
    }
}
int main()
{
    int i;
    f>>n>>m;
    for(i=1; i<=m; i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }
    sort(v+1,v+m+1,compar);
    for(i=1;i<=n;i++)
    {
        t[i]=i;
        h[i]=1;
    }
    kruskal();
    g<<ct<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
    {
        int j=mu[i];
        g<<v[j].x<<" "<<v[j].y<<'\n';
    }
    return 0;
}