#include <bits/stdc++.h>
#define ll long long

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct Edge {
    int x, y, cost;
    bool operator <(Edge const& other){
        return cost < other.cost;
    }
};
vector<int> parent, rang;
int find(int node) {
    if (parent[node] == node) {
        return node;
    }
    return parent[node] = find(parent[node]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        if (rang[a] < rang[b]) {
            swap(a, b);
        }
        parent[b] = a;
        if (rang[a] == rang[b]) {
            rang[a]++;
        }
    }
}
void solve() {
    int n, m;
    fin >> n >> m;
    parent.resize(n + 1);
    rang.resize(n + 1);
    for (int i = 0; i <= n; i++) {
        parent[i] = i;
        rang[i] = 0;
    }
    vector<Edge> adj;
    while (m--) {
        int x, y, cost;
        fin >> x >> y >> cost;
        adj.push_back({x, y, cost});
    }
    vector<Edge> ans;
    sort(adj.begin(), adj.end());
    int cost = 0;
    for (auto e : adj) {
        if (find(e.x) != find(e.y)) {
            cost += e.cost;
            ans.push_back(e);
            merge(e.x, e.y);
        }
    }
    fout << cost << endl;
    fout << n - 1 << endl;
    for (auto v : ans) {
        fout << v.x << " " << v.y << endl;
    }
}

int main() {
    int t = 1;
    // fin >> t;
    while (t--) {
        solve();
    }
}