#include <bits/stdc++.h>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, i, t[200005], lg[200005], s, a, b, c;
vector<pair<int, int>>v[200005], r;
pair<int, pair<int, int>>muchie[400005];
int radacina(int a) {
    if (t[a]!=a) {
        t[a]=radacina(t[a]);
    }
    return t[a];
}
void uneste(int a, int b) {
    if (lg[a]>lg[b]) {t[b]=a; lg[a]+=lg[b];}
    else {t[a]=b; lg[b]+=lg[a];}
}
int main()
{
    fin>>n>>m;
    for (i=1; i<=n; i++) {
        t[i]=i;
        lg[i]=1;
    }
    for (i=1; i<=m; i++) {
        fin>>a>>b>>c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
        muchie[i]={c, {a, b}};
    }
    sort(muchie+1, muchie+m+1);
    for (i=1; i<=m; i++) {
        int x=muchie[i].second.first;
        int y=muchie[i].second.second;
        int radx=radacina(x);
        int rady=radacina(y);
        if (radx!=rady) {
            uneste(radx, rady);
            s+=muchie[i].first;
            r.push_back({x, y});
        }
    }
    fout<<s<<'\n'<<n-1<<'\n';
    for (auto x:r) fout<<x.first<<' '<<x.second<<'\n';
    return 0;
}