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

#define NMax 400005
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 = 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()
{
    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;
}