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

#define NMax 200002
using namespace std;
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)
        x = r[x];
    return x;
}
void kruskal(){
    for(int i = 1; i <= n; ++i){
        r[i] = i;
        rang[i] = 1;
    }
    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;

            if(rang[Rx] > rang[Ry]){
                r[Ry] = Rx;
                rang[Rx] += rang[Ry];
            }else{
                r[Rx] = r[Ry];
                rang[Ry] += rang[Rx];
            }
        }
    }
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m; ++i){
        scanf("%d%d%d",&G[i].x,&G[i].y,&G[i].c);
    }
    sort(G + 1, G + 1 + m,cmp);
    kruskal();
    printf("%d\n%d\n",cost,n - 1);
    for(int i = 1; i < n; ++i){
        printf("%d %d\n",sol[i].x, sol[i].y);
    }
    return 0;
}