#include <bits/stdc++.h>

using namespace std;

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

int n,ct,tata[200100],h[200100];


struct Muchie
{
    int x,y,c;
}v[400100];

struct
{
    int X,Y;
}V[400100];

int muchie(int x,int y)
{
    int r1,r2,x1,y1,C;

    r1=x;r2=y;

    while(tata[r1]!=r1)r1=tata[r1];
    while(tata[r2]!=r2)r2=tata[r2];


    if(r1==r2)return 0;

    while(tata[x]!=r1)
    {
        x1=tata[x];
        tata[x]=r1;
        x=x1;
    }

    while(tata[y]!=r2)
    {
        y1=tata[y];
        tata[y]=r2;
        y=y1;
    }


    if(h[r1]>h[r2]){tata[r2]=r1;C=r1;}
    else {tata[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++;
            V[k].X=v[i].x;
            V[k].Y=v[i].y;
        }
        i++;
    }

}









int compare(Muchie A,Muchie B)
{
    return(A.c<B.c);
}


int m,i;

int main()
{
    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,compare);

    for(i=1;i<=n;i++)h[i]=1;
    for(i=1;i<=n;i++)tata[i]=i;

    kruskal();

    g<<ct<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=n-1;i++)
    {
        g<<V[i].X<<" "<<V[i].Y<<'\n';
    }
    return 0;
}