#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int INF = 1e5;
int n, m, cost, viz[200001], dad[200001];
vector<pair<int, int>> g[200001], edges;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

void prim(int r){
    pq.push({0, r});
    while (!pq.empty())
    {
        int u = pq.top().second, c1 = pq.top().first;
        pq.pop();
        if(!viz[u]) cost += c1, viz[u] = 1, edges.push_back({u, dad[u]});
        for(auto e : g[u]){
            int v = e.first, c = e.second;
            if(!viz[v]) pq.push({c, v}), dad[v] = u;
        }
    }
}

int main(){
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y, c;
        fin >> x >> y >> c;
        g[x].push_back({y, c}), g[y].push_back({x, c});
    }
    prim(1);
    fout << cost << '\n';
    fout << edges.size() - 1 << '\n';
    for(int i = 1; i < edges.size(); i++) fout << edges[i].first << ' ' << edges[i].second << '\n';
    fin.close();
    fout.close();
    return 0;
}