#include <iostream>
#include <fstream>
#include <algorithm>
#define nmax 10001
#define mmax 10001
#define pp pair<int,pair<int,int> >
#define c first
#define x second.first
#define y second.second

using namespace std;

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

int n,m,rang[nmax],t[nmax],s[mmax],sol,nr;
pair<int,pair<int,int> > g[mmax];

void read(){
    int i;
    f >> n >> m;
    for(i=1;i<=m;++i)
        f >> g[i].x >> g[i].y >> g[i].c;
    sort(g+1,g+1+m);
}

int multime(int nod){
    if(t[nod]!=nod)
        t[nod]=multime(t[nod]);
    return t[nod];
}

void join(int i,int j){
    i=multime(i);
    j=multime(j);
    if(i==j) return;

    if(rang[i]<rang[j]) t[i]=j;
    else t[j]=i;
    if(rang[i]==rang[j]) ++rang[i];
}

void apm(){
    int k,i,j,cost;
    for(k=1;k<=m;++k)
        t[k]=k;
    for(k=1;k<=m;++k){
        i=g[k].x;
        j=g[k].y;
        cost=g[k].c;
        if(multime(i)!=multime(j)){
            join(i,j);
            sol+=cost;
            s[++nr]=k;
        }
    }
}

void afis(){
    o << rez << '\n' << n-1 << '\n';
    for(i=1;i<=nr;++i){
        k=s[i];
        o << g[k].x << " " << g[k].y << '\n';
    }
}

int main()
{
    read();
    apm();
    afis();

    return 0;
}