#include <bits/stdc++.h>

using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

int n, m;
vector<pair<int, int>> g[200005];
struct edge {
    int fs, sd;
    int weight;
};
struct CompareWeight {
    bool operator()(edge a, edge b) {
        return a.weight > b.weight;
    }
};
vector<pair<int, int>> mst; int mst_size;
bool used[200005];

bool customSort(edge a, edge b) {
    return a.weight < b.weight;
}

int main() {
    in >> n >> m;
    for(int i = 1; i <= m; i++) {
        int u, v, w; in >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    priority_queue<edge, vector<edge>, CompareWeight> pq;
    used[1] = true;
    for(auto elem : g[1])
        pq.push({1, elem.first, elem.second});
    while(!pq.empty()) {
        auto crt = pq.top();
        pq.pop();
        if(used[crt.sd]) continue;
        used[crt.sd] = true;
        mst_size += crt.weight;
        mst.push_back({crt.fs, crt.sd});
        for(auto elem : g[crt.sd]) {
            if(!used[elem.first])
                pq.push({crt.sd, elem.first, elem.second});
        }
    }
    out << mst_size << '\n';
    out << mst.size() << '\n';
    for(auto elem : mst)
        out << elem.first << ' ' << elem.second << '\n';
    return 0;
}