#include <bits/stdc++.h>
#define NMAX 200003
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
vector <pair <int, pair <int, int> >> muchii;
vector <int> ans;
int tata [NMAX], h [NMAX];
int n, m, x, y, c, cost;
bool cmp (pair <int, pair <int, int> > A, pair <int, pair <int, int> > B){
    return A.first < B.first;
}
int findl (int x){
    if (tata [x] == x)
        return x;
    tata [x] = findl (tata [x]);
    return tata [x];
}
int main (){
    fin >> n >> m;
    for (int i = 1; i <= m; i ++){
        fin >> x >> y >> c;
        muchii.push_back ({c, {x, y}});
    }
    for (int i = 1; i <= n; i ++)
        tata [i] = i;
    sort (muchii.begin (), muchii.end (), cmp);
    for (int i = 0; i < muchii.size (); i ++){
        int a = muchii [i].second.first;
        int b = muchii [i].second.second;
        a = findl (a);
        b = findl (b);
        if (a == b) continue;
        if (h [a] >= h [b])
            tata [b] = a;
        else tata[a] = b;
        if (h [a] == h [b])
            h [a] ++;
        cost += muchii [i].first;
        ans.push_back (i);
    }
    fout << cost << '\n';
    fout << ans.size () << '\n';
    for (auto i : ans)
        fout << muchii [i].second.first << " " << muchii [i].second.second << '\n';
}