#include <fstream>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct muchie{
    unsigned int x;
    unsigned int y;
    int c;
};
struct muchief{
    unsigned int x;
    unsigned int y;
};
muchie U[400000];
muchief FIN[400000];
long n,m,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(){
    int L[200000],nr1,nr2;
    for(int j=1; j<=n; j++) L[j]=j;
    int k=0,i=0;
    while(k<n-1){
        if(L[U[i].x]!=L[U[i].y]){
            FIN[k].x=U[i].x;
            FIN[k++].y=U[i].y;
            ct+=U[i].c;
            nr1=L[U[i].x]; nr2=L[U[i].y];
            for(int j=1;j<=n;j++)
                if(L[j]==nr2) L[j]=nr1;
        }
        i++;
    }
    return k;
}
int main()
{   int k;
    citire();
    sort();
    k=apm();
    g<<ct<<'\n'<<k<<'\n';
    for(int i=0; i<k; i++)
        g<<FIN[i].x<<' '<<FIN[i].y<<'\n';
    return 0;
}