/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>

using namespace std;

const int N = 2e5;
const int M = 4e5;

struct ura {
    int from, to, cost;

    bool operator < (const ura a) const {
        return cost < a.cost;
    }
};
ura v[5 + M];
int parent[5 + N], szg[5 + N];
pair <int,int> sol[5 + N];

int n, m;

int Find(int x) {
    int y;
    for(y = x; parent[y] != y; y = parent[y]);

    for(; parent[x] != x;) { // compresie
        int cx = parent[x];
        parent[x] = y;
        x = cx;
    }

    return y;
}

void Unite(int x, int y) {
    if(szg[x] > szg[y]) {
        parent[y] = x;
        szg[x] += szg[y];
        szg[y] = szg[x];
    } else {
        parent[x] = y;
        szg[y] += szg[x];
        szg[x] = szg[y];
    }
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int costm(0), cnt(0);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++) scanf("%d%d%d", &v[i].from, &v[i].to, &v[i].cost);
    sort(v + 1, v + m + 1);

    for(int i = 1; i <= n; i++){
        parent[i] = i;
        szg[i] = 1;
    }

    for(int i = 1; i <= m; i++){
        int x, y;
        x = v[i].from;
        y = v[i].to;
        if(Find(x) != Find(y)){
            costm += v[i].cost;
            sol[++cnt] = make_pair(x, y);
            Unite(Find(x), Find(y));
        }
    }

    printf("%d\n%d\n", costm, cnt);

    for(int i = 1; i <= cnt; i++) printf("%d %d\n", sol[i].first, sol[i].second);
    return 0;
}