#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
int n, m, t[200005];
vector <pair<int, int>> rez;
struct st
{
    int i, j, cost;
};
bool cmp(const st &a, const st &b)
{
    return a.cost < b.cost;
}
st x[400005];
int f(int u)
{
    if(t[u] == u)
        return u;
    return t[u] = f(t[u]);
}
int main()
{
    in >> n >> m;
    for(int i = 0; i < m; i ++)
        in >> x[i].i >> x[i].j >> x[i].cost;
    sort(x, x + m, cmp);
    for(int i = 1; i <= n; i ++)
        t[i] = i;
    int s = 0;
    for(int i = 0; i < m; i ++)
    {
        if(f(x[i].i) != f(x[i].j))
        {
            s += x[i].cost;
            rez.push_back(make_pair(x[i].i, x[i].j));
            int a = f(x[i].i);
            int b = f(x[i].j);
            if(a != b)
                t[b] = a;
        }
    }
    out << s << '\n' << n - 1 << '\n';
    for(auto it : rez)
        out << it.second << " " << it.first << '\n';
    return 0;
}