#include <bits/stdc++.h>

using namespace std;

struct edge{
    int x,y,cost;
    bool used;
}edges[400005];

int root[100005], depth[100005];

inline int getRoot(int x){
    if(root[x] != x){
        root[x] = getRoot(root[x]);
    }
    return root[x];
}

void unite(int x, int y){
    x = getRoot(x);
    y = getRoot(y);
    if(x == y){
        return;
    }
    if(depth[x] > depth[y]){
        root[y] = x;
    }else{
        root[x] = y;
    }
}

bool areUnion(int x, int y){
    x = getRoot(x);
    y = getRoot(y);
    return x == y;
}

bool comp(edge a, edge b){
    return a.cost < b.cost;
}

int main(){
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n,m,i,op,x,y,c;
    scanf("%d %d", &n, &m);
    for(i = 1;i <= n;i++){
        root[i] = i;
        depth[i] = 1;
    }
    for(i = 1;i <= m;i++){
        scanf("%d %d %d", &edges[i].x, &edges[i].y, &edges[i].cost);
    }
    sort(edges + 1, edges + m + 1, comp);
    int ans = 0;
    for(i = 1;i <= m;i++){
        if(areUnion(edges[i].x, edges[i].y) == 0){
            ans += edges[i].cost;
            unite(edges[i].x, edges[i].y);
            edges[i].used = 1;
        }
    }
    printf("%d\n%d\n", ans, n - 1);
    for(i = 1;i <= m;i++){
        if(edges[i].used){
            printf("%d %d\n", edges[i].x, edges[i].y);
        }
    }
    return 0;
}