#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{
    int x;
    int y;
    int c;
    };
muchie FIN[200001];
muchie U[400001];
long n,m;
int ct;
void citire(){
    f>>n>>m;
    for(int i=1; i<=m; i++)
        f>>U[i].y>>U[i].x>>U[i].c;
}
void sort(){
    muchie aux;
    for(int i=1; i<=m-1; i++)
        for(int j=i+1; j<=m; j++)
            if(U[i].c>U[j].c){
                aux=U[i];
                U[i]=U[j];
                U[j]=aux;
            }
}
int apm_prim(){
    int V[400001],i;
    V[U[1].x]=1;V[U[1].y]=1;
    FIN[0].x=U[1].x; FIN[0].y=U[1].y;
    ct=U[1].c;
    for(int k=1; k<n-1; k++){
        i=1;
        while(V[U[i].x]==V[U[i].y]) i++;
        FIN[k].x=U[i].x; FIN[k].y=U[i].y;
        if(V[U[i].x]) V[U[i].y]=1;
        else    V[U[i].x]=1;
        ct+=U[i].c;
    }
}
int main()
{
    citire();
    sort();
    apm_prim();
    g<<ct<<'\n'<<n-1<<'\n';
    for(int i=0; i<n-1; i++)
        g<<FIN[i].x<<' '<<FIN[i].y<<'\n';
    return 0;
}