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

int N, M, root[400005], ranking[400005], minCost;

struct Edge {
    int x, y, cost;
};

vector <Edge> v;
vector <pair<int, int>> ans;

bool cmp(Edge a, Edge b) {
    return a.cost < b.cost;
}

int findRoot(int node) {
    while(root[node] != node) {
        node = root[node];
    }
    return node;
}

void letsUnite(int x, int y) {
    if(ranking[x] < ranking[y]) {
        root[x] = y;
    } else if(ranking[x] > ranking[y]) {
        root[y] = x;
    } else {
        root[x] = y;
        ranking[y]++;
    }
}

int main() {

    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    
    scanf("%d%d", &N, &M);
    for(int i = 1; i <= M; i++) {
        int x, y, cost;
        scanf("%d%d%d", &x, &y, &cost);
        v.push_back({x, y, cost});
    }

    sort(v.begin(), v.end(), cmp);

    for(int i = 1; i <= N; i++) {
        root[i] = i;
        ranking[i] = 1;
    }

    for(auto edge : v) {
        int x_root = findRoot(edge.x),
            y_root = findRoot(edge.y);
        
        if(x_root != y_root) {
            letsUnite(x_root, y_root);
            minCost += edge.cost;
            ans.push_back({edge.x, edge.y});
        }
    }

    printf("%d\n%d\n", minCost, ans.size());
    for(auto edge : ans) {
        printf("%d %d\n", edge.first, edge.second);
    }
    return 0;
}