#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;
    }
};
int find(int node, vector<int>& parent) {
    if (parent[node] == node) {
        return node;
    }
    return parent[node] = find(parent[node], parent);
}

void merge(int a, int b, vector<int>& parent, vector<int>& rang) {
    a = find(a, parent);
    b = find(b, parent);
    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;
    vector<Edge> adj;
    while (m--) {
        int x, y, cost;
        fin >> x >> y >> cost;
        x--;
        y--;
        adj.push_back({x, y, cost});
    }
    vector<int> parent(n);
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
    vector<int> rang(n, 0);
    vector<Edge> ans;
    sort(adj.begin(), adj.end());
    int cost = 0;
    for (auto e : adj) {
        if (find(e.x, parent) != find(e.y, parent)) {
            cost += e.cost;
            ans.push_back(e);
            merge(e.x, e.y, parent, rang);
        }
    }
    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();
    }
}