#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define MAX_VALUE 999999999
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
struct muchie {
    int x, y, d;
    bool used;
};
vector <muchie> a;
vector <int> rankx;
vector <int> apm;
int n, m, x, y, z, R;
bool comp(muchie a, muchie b) {
    return a.d < b.d;
}
int find(int x) {
    if(apm[x] != x) {
        apm[x] = find(apm[x]);
    }
    return apm[x];
}
void Union(int oldValue, int newValue) {
    apm[oldValue] = apm[newValue];
}
int main()
{
    fin>>n>>m;
    muchie t;
    for(int i = 1; i <= m; i++) {
        fin>>x>>y>>z;
        t.x = x;
        t.y = y;
        t.d = z;
        t.used = false;
        a.push_back(t);
    }
    apm.push_back(0);
    rankx.resize(n + 1);
    for(int i = 1; i <= n; i++) {
        apm.push_back(i);
    }
    sort(a.begin(), a.end(), comp);
    int cost = 0;
    for(int i = 0; i < a.size(); i++) {
        if(find(a[i].x) != find(a[i].y)) {
            cost = cost + a[i].d;
            a[i].used = true;
            if(rankx[a[i].x] < rankx[a[i].y]) {
                Union(find(a[i].x), find(a[i].y));
                rankx[a[i].y]++;
            } else {
                Union(find(a[i].y), find(a[i].x));
                rankx[a[i].x]++;
            }
        }
    }
    fout<<cost<<'\n';
    fout<<n - 1<<'\n';
    for(int i = 0; i < m; i++) {
        if(a[i].used) {
            fout<<a[i].y<<' '<<a[i].x<<'\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}