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

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

vector<tuple<int, int, int> > muchii;
int n, m;
int v[200005], rang[200005];
vector<pair<int, int> > sol;
int cost;

void citire() {
    fin >> n >> m;
    int a, b, c;
    for(int i = 1; i <= m; i++) {
        fin >> a >> b >> c;
        muchii.push_back(make_tuple(c, a, b));
    }
}

int root(int x) {
    if(!v[x]) return x;
    v[x] = root(v[x]);
    return v[x];
}

int Union(int x, int y) {
    int rx = root(x);
    int ry = root(y);

    if(rx == ry)
        return 0;
    if(rang[rx] > rang[ry])
        v[ry] = rx;
    else {
        if(rang[rx] == rang[ry])
            rang[rx]++;
        v[rx] = ry;
    }
    return 1;
}


void solve() {
    sort(muchii.begin(), muchii.end());
    for(int i = 0; i < muchii.size(); i++)
        if(Union(get<1>(muchii[i]), get<2>(muchii[i]) ) ) {
            cost += get<0>(muchii[i]);
            sol.push_back({get<1>(muchii[i]), get<2>(muchii[i])});
        }
}

void afis() {
    fout << cost << '\n' << sol.size() << '\n';
    for(int i = 0; i < sol.size(); i++)
        fout << sol[i].first << ' ' << sol[i].second << '\n';
}

int main() {
    citire();
    solve();
    afis();
}