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

vector < tuple < int, int, int >> v;
int n, m, cost;
int usedNode[400005], usedEdge[400005];

bool cmp(const tuple < int, int, int > & a,
         const tuple < int, int, int > & b) {
    return (get < 2 > (a) < get < 2 > (b));
}

int main() {
    freopen("catun.in", "r", stdin);
    freopen("catun.out", "w", stdout);

    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        scanf("%d%d%d", &x, &y, &cost);
        v.emplace_back(x - 1, y - 1, cost);
    }
    sort(v.begin(), v.end(), cmp);

    usedNode[0] = 1;
    for (int p = 1; p < n; ++p) {
        for (int i = 0; i < m; i++) {
            if (usedNode[get<0>(v[i])] != usedNode[get<1>(v[i])]) {
                cost += get<2>(v[i]);
                usedNode[get<0>(v[i])] = 1;
                usedNode[get<1>(v[i])] = 1;
                usedEdge[i] = 1;
                break;
            }
        }
    }

    printf("%d\n%d\n", cost, n - 1);
    for (int i = 0; i < m; ++i) {
        if (usedEdge[i]) {
            printf("%d %d\n", get<0>(v[i]) + 1, get<1>(v[i]) + 1);
        }
    }
    return 0;
}