#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 = 200005;
int N, M;
int lg[NMax + 1], father[NMax + 1];
struct point {int x, y, c;} v[2 * NMax + 1], edge[2 * NMax + 1];

inline int Find(int x){

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

inline void Union(int tx, int ty){

    if (lg[tx] == lg[ty]){

            lg[tx] ++;
            father[ty] = tx;
    }
    else
        if (lg[tx] > lg[ty])
            father[ty] = tx;
    else
        father[tx] = ty;

}

inline 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);
}