#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

FILE *fin = freopen("apm.in", "r", stdin);
FILE *fout = freopen("apm.out", "w", stdout);

const int NMax = 400000;
int N, M;
int lg[NMax + 1], father[NMax + 1];
struct point {int x, y, c;} v[NMax + 1], edge[NMax + 1];

int Find(int x){

   while (father[x] != x)
        x = father[x];
   return x;
}

void Union(int x, int y){

    if (lg[x] > lg[y])
        father[y] = x;
    else
        father[x] = y;

    if (lg[x] == lg[y])
        lg[x] ++;
}

bool cmp(point a, point b){
    return a.c < b.c;
}

int main(){

    scanf("%d%d", &N, &M);

    for (int i = 1; i <= M; i++){
        scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].c);
    }

    sort (v + 1, v + 1 + M, cmp);

    for (int i = 1; i <= N; i++)
        father[i] = i,
        lg[i] = 1;

    int cnt = 0, X, Y, sum = 0;
    for (int i = 1; i <= M; i++){

        X = Find(v[i].x);
        Y = Find(v[i].y);

        if (X != Y){
            sum += v[i].c;
            Union(X, Y);
            edge[++cnt] = v[i];
        }
    }

    printf("%d\n%d\n", sum, cnt);
    for (int i = 1; i <= cnt; i++)
        printf("%d %d\n", edge[i].x, edge[i].y);
}