#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
using ll = long long;
struct Item {
    int v;
    int p;
    int w;
    bool operator<(Item const& other) const {
        return w > other.w;
    }
};
int main() {
    int N, M;
    if (!(fin >> N >> M)) return 0;
    vector<vector<pair<int,int>>> adj(N + 1);
    for (int i = 0; i < M; ++i) {
        int x, y, c;
        fin >> x >> y >> c;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }
    if (N <= 1) {
        cout << 0 << '\n' << 0 << '\n';
        return 0;
    }
    vector<char> used(N + 1, 0);
    priority_queue<Item> pq;
    pq.push({1, -1, 0});
    ll total = 0;
    vector<pair<int,int>> edges;
    edges.reserve(N - 1);
    while (!pq.empty() && (int)edges.size() < N - 1) {
        Item it = pq.top(); pq.pop();
        int v = it.v;
        if (used[v]) continue;
        used[v] = 1;
        if (it.p != -1) {
            total += it.w;
            edges.push_back({v, it.p});
        }
        for (auto &e : adj[v]) {
            int to = e.first;
            int w = e.second;
            if (!used[to]) pq.push({to, v, w});
        }
    }
    sort(edges.begin(), edges.end());
    fout << total << '\n';
    fout << edges.size() << '\n';
    for (auto &e : edges) fout << e.first << ' ' << e.second << '\n';
    return 0;
}