#include <bits/stdc++.h>

using namespace std;

vector<pair<int, int>> g[200005];
int n,m, v[200005];

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

    priority_queue<pair<int, pair<int, int>>> pq;
    vector<pair<int, int>> ans;
    int cost = 0;
    for(auto x: g[1]) pq.push({-x.second, {1, x.first}});
    v[1] = 1;

    while(!pq.empty()) {
        int x = pq.top().second.first;
        int y = pq.top().second.second;
        int c = -pq.top().first;
        pq.pop();

        if(v[y]) continue;
        v[y] = 1;
        ans.push_back({x, y});
        cost += c;

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