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

ifstream fin("apm.in");
ofstream fout("apm.out");

int n, m, tt[200001], rg[200001], k, total;
pair<int, int> p[200001];

struct muchie{
    int x, y, cost;
} v[400001];

bool fcmp(muchie a, muchie b){
    return a.cost < b.cost;
}

void read(){

    fin >> n >> m;

    for(int i = 1; i <= m; i++)
        fin >> v[i].x >> v[i].y >> v[i].cost;

    sort(v + 1, v + m + 1, fcmp);

    for(int i = 1; i <= n; i++)
        tt[i] = i, rg[i] = 1;
}

int rad(int nod){
    while(tt[nod] != nod)
        nod = tt[nod];
    return nod;
}

void unire(int x, int y){
    if(rg[x] < rg[y])
        tt[x] = y;
    else if(rg[x] > rg[y])
        tt[y] = x;
    else
        tt[x] = y, rg[y]++;
}

void solve(){
    for(int i = 1; i <= m; i++){
        int tatax = rad(v[i].x);
        int tatay = rad(v[i].y);

        if(tatax != tatay){
            unire(tatax, tatay);
            p[++k].first = v[i].x;
            p[k].second = v[i].y;
            total += v[i].cost;
        }
    }
}

void print(){
    fout << total << '\n' << k << '\n';
    for(int i = 1; i <= k; i++)
        fout << p[i].first << ' ' << p[i].second << '\n';
}

int main(){

    read();
    solve();
    print();
}