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

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

int t[200005];
int inalt[200005];
int x,y,c, n,m;
set < pair < int, pair < int , int > > > s; /// set din {cost , {x, y} }
int sum = 0;

queue < pair < int ,int > > q;

int radacina(int x) {
    if (t[x]==0) return x;
    else return radacina(t[x]);
}

int main()
{
    f >> n >> m;
    for (int i=1;i<=m;i++) {
        f >> x >> y >> c;
        s.insert({c, {x,y}});
    }
    while (!s.empty()) {
        int cost = s.begin()->first;
        x = s.begin()->second.first;
        y = s.begin()->second.second;
        s.erase(s.begin());
        int rad_x = radacina(x);
        int rad_y = radacina(y);
        if (rad_x != rad_y) {
            if (inalt[rad_x] > inalt[rad_y]) {
                t[rad_y] = rad_x;
            }
            else if (inalt[rad_y] > inalt[rad_x]) {
                t[rad_x] = rad_y;
            }
            else {
                t[rad_y] = rad_x;
                inalt[rad_x]++;
            }
            q.push({x, y});
            sum += cost;
        }
    }
    g << sum << '\n';
    g << n-1 << '\n';
    while (!q.empty()) {
        g << q.front().first << " " << q.front().second << '\n';
        q.pop();
    }
    return 0;
}