#include <bits/stdc++.h>

using namespace std;

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

int n, m, x, y, c, ans, muchii;
int tata[200005], com[200005];

struct noduri {
    int x, y, c;
}a[400005];

vector<pair<int,int> > G;

bool comp(noduri a, noduri b){
    return a.c < b.c;
}

int root(int nod){
    int r=nod, y=nod, aux;
    while(tata[r])
        r = tata[r];
    while(y != r){
        aux = tata[y];
        tata[y] = r;
        y = aux;
    }

    return r;
}

void unite(int x, int y){
    if (com[x] > com[y])
        tata[y] = x;
    else{
        tata[x] = y;
        if (com[x] == com[y])
            com[y]++;
    }
}

int main()
{
    fin >> n >> m;
    for (int i=1; i<=m; i++)
        fin >> a[i].x >> a[i].y >> a[i].c;
    sort(a+1, a+m+1, comp);
    for (int i=1; i<=m; i++){
        int nod1=root(a[i].x);
        int nod2=root(a[i].y);
        if (nod1 != nod2){
            unite(nod1, nod2);
            muchii++;
            ans += a[i].c;
            G.push_back({a[i].x, a[i].y});
        }
    }
    fout << ans << '\n' << muchii << '\n';
    for (auto it : G)
        fout << it.first << ' ' << it.second << '\n';
    return 0;
}