#include <bits/stdc++.h>

using namespace std;

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

int i, j, N, M, x, y, c, rez;
bool prez[200009];
vector <pair <int, int> > v[200009];
queue <pair <int, int> > q;

int rezolvare(int poz){
    int minim = 100000;
    int reper = 0;
    for (int ii = 0; ii < v[poz].size(); ii++){
        if (v[poz][ii].second < minim && !prez[v[poz][ii].first]){
            minim = v[poz][ii].second;
            reper = v[poz][ii].first;
        }
    }
    if (reper){
        prez[reper] = true;
        q.push(make_pair(poz, reper));
        return minim + rezolvare(reper);
    }
    else
        return 0;
}

int main()
{
    f >> N >> M;
    while(M--){
        f >> x >> y >> c;
        v[x].push_back(make_pair(y, c));
        v[y].push_back(make_pair(x, c));
    }
    for (i = 1; i <= N; i++){
        prez[i] = true;
        rez += rezolvare(i);
    }
    g << rez << "\n";
    g << N - 1 << "\n";
    while(!q.empty()){
        g << q.front().first << " " << q.front().second << "\n";
        q.pop();
    }

    return 0;
}