#include <bits/stdc++.h>
using namespace std;

typedef struct lol{
    int x, y, c;
} much;

much M[400010];
int n, m, p[200010], cost, k;
bool u[400010];

int find(int a){
    if (a == p[a]) return a;
    int r = find(p[a]);
    p[a] = r;
    return r;
}

void unite(int a, int b){
    a = find(a);
    b = find(b);
    p[a] = b;
}

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

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    ifstream cin ("apm.in");
    ofstream cout ("apm.out");
    cin >> n >> m;
    for (int i=1; i<=m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        M[i] = {a, b, c};
    }
    for (int i=1; i<=m; i++) p[i] = i;
    sort(M+1, M+1+m, cmp);
    for (int i=1; i<=m; i++){
        if (find(M[i].x) != find(M[i].y)) unite(M[i].x, M[i].y), cost += M[i].c, k++, u[i] = 1;
    }
    cout << cost << "\n" << k << "\n";
    for (int i=1; i<=m; i++){
        if (u[i]) cout << M[i].x << " " << M[i].y << "\n";
    }
    return 0;
}