#include <bits/stdc++.h>

using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct muchie{
    int x, y, w;
};
bool cmp (muchie a, muchie b){
    return a.w < b.w;
}
vector<muchie>v;
vector<int>parent;
int par(int u){
    if (parent[u] == u)
        return u;
    return parent[u] = par(parent[u]);
}
void unite(int x, int y){
    auto p1 = par(x);
    auto p2 = par(y);
    if (p1 != p2){
        parent[p2] = p1;
    }
}
signed main(){
    int n, m;
    fin >> n >> m;
    v.resize(m);
    parent.resize(n + 5);
    iota(parent.begin(), parent.end(), 0LL);
    for (int i = 0; i < m; ++i)
        fin >> v[i].x >> v[i].y >> v[i].w;
    sort(v.begin(), v.end(), cmp);
    int ans = 0;
    vector<muchie>sol;
    for (int i = 0; i < m && sol.size() != n - 1; ++i){
         if (par(v[i].x) != par(v[i].y)){
            ans += v[i].w;
            unite(v[i].x, v[i].y);
            sol.push_back(v[i]);
         }
    }
    fout << ans << "\n" << (int)sol.size() << "\n";
    for (auto &it : sol)
        fout << it.x << " " << it.y << "\n";
    return 0;
}