#include <bits/stdc++.h>
using namespace std;

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

int n, m, a, b, c, ansCost;
bool visited[200001];
vector<pair<int, int>> lad[200001], ans;

class Compare {
public:
    inline bool operator()(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
        return a.first > b.first;
    }
};
int main() {
    f >> n >> m;
    for(int i = 1; i <= m; i ++){
        f >> a >> b >> c;
        lad[a].push_back(make_pair(b,c));
        lad[b].push_back(make_pair(a,c));
    }

    priority_queue <pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, Compare> q;

    for(auto nb : lad[1]) q.push(make_pair(nb.second, make_pair(1, nb.first)));
    visited[1] = true;

    while(!q.empty()){
        c = q.top().first;
        a = q.top().second.first;
        b = q.top().second.second;
        q.pop();

        if(visited[b]) continue;

        visited[b] = true;
        ans.push_back(make_pair(a,b));
        ansCost += c;

        for(auto nb : lad[b]){
            if(!visited[nb.first]){
                q.push(make_pair(nb.second, make_pair(b, nb.first)));
            }
        }
    }

    g << ansCost << "\n" << ans.size() << "\n";
    for(auto a : ans){
        g << a.first << " " << a.second << "\n";
    }

    return 0;
}