#include <bits/stdc++.h>

using namespace std;

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

priority_queue<pair<int, pair<int, int>>> coada;
vector<pair<int, int>> graf[200001];
int n,m, v[200001], cost;

int main() {
    fin >> n >> m;
    int x, y, c;
    while(m--) {
        fin >> x >> y >> c;
        graf[x].push_back({y, c});
        graf[y].push_back({x, c});
    }

    vector<pair<int, int>> ans;
    for(auto x: graf[1]) coada.push({-x.second, {1, x.first}});
    v[1] = 1;

    while(!coada.empty()) {
         x = coada.top().second.first;
         y = coada.top().second.second;
         c = -coada.top().first;
        coada.pop();
        if(v[y]) continue;
        v[y] = 1;
        ans.push_back({x, y});
        cost += c;

        for(auto next: graf[y]) {
            if(!v[next.first])  {
                coada.push({-next.second, {y, next.first}});
            }
        }
    }
    fout << cost << '\n' << ans.size() << '\n';
    for(auto p: ans) fout << p.first << ' ' << p.second << '\n';
}