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

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

int n, m, tata[200001], lg[200001], x, y;

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

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

void unesc(int radx, int rady){
    if(lg[radx] < lg[rady])
        tata[radx] = rady;
    else if(lg[radx] > lg[rady])
        tata[rady] = radx;
    else
        tata[rady] = radx, lg[radx]++;
}

void sunt(int radx, int rady){
    if(radx == rady)
        fout << "DA";
    else
        fout << "NU";
    fout << '\n';
}

int rad(int x){
    while(x != tata[x])
        x = tata[x];
    return x;
}

int main(){

    fin >> n >> m;
    for(int i = 1; i <= n; i++)
        tata[i] = i, lg[i] = 1;

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

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

    int k = 1, anscost = 0, i = 0;
    vector<pair<int, int> > rez;
    while(i < n - 1){
        int radx = rad(muchii[k].x);
        int rady = rad(muchii[k].y);

        if(radx != rady){
            unesc(radx, rady);
            anscost += muchii[k].cost;
            rez[k];
            rez.push_back({muchii[k].x, muchii[k].y});
            i++;
        }
        k++;
    }

    fout << anscost << '\n' << n - 1 << '\n';
    for(int i = 0; i < n - 1; i++)
        fout << rez[i].first << ' ' << rez[i].second << '\n';
}