#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <cstring>
#include <iomanip>
#include <fstream>

#define NMax 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

struct muchie{
    int x,y,c;
}G[NMax],sol[NMax];

int n,m,Rx,Ry,cost,muchii;
int r[NMax],rang[NMax];

int cmp(muchie x,muchie y){
    if(x.c > y.c)
        return 0;
    return 1;
}
int root(int x){
    while(r[x])
        x = r[x];
    return x;
}
void kruskal(){
    for(int i = 1; i <= m && muchii < n - 1; ++i){
        Rx = root(G[i].x);
        Ry = root(G[i].y);

        if(Rx != Ry){
            sol[++muchii] = G[i];
            cost += G[i].c;

            r[Rx] = Ry;
        }
    }
}
int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; ++i){
        f >> G[i].x >> G[i].y >> G[i].c;
    }
    sort(G + 1, G + 1 + m,cmp);
    kruskal();
    g << cost <<"\n" << n - 1 <<"\n";
    for(int i = 1; i < n; ++i){
        g << sol[i].x <<" " << sol[i].y <<"\n";
    }
    return 0;
}