#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
ifstream f("apm.in");
ofstream g("apm.out");
int n, m, c, T[N], getRoot(int);
queue <pair<int, int>> q;
vector <tuple<int, int, int>> v;
int main()
{
    f >> n >> m;
    cout << n << ' ' << m;
    for(; m; m--)
    {
        int x, y, c;
        f >> x >> y >> c;
        v.push_back(make_tuple(c, x, y));
    }
    for(int i = 1; i <= n; i++)
        T[i] = i;
    sort(v.begin(), v.end());
    for(auto val:v)
    {
        int x, y, rx, ry, cost;
        tie(cost, x, y) = val;
        rx = getRoot(x);
        ry = getRoot(y);
        if(rx != ry)
        {
            T[rx] = ry;
            c += cost;
            q.push(make_pair(y, x));
        }
    }
    g << c << '\n' << q.size() << '\n';
    while(!q.empty())
    {
        g << q.front().first << ' ' << q.front().second << '\n';
        q.pop();
    }
    return 0;
}
int getRoot(int nod)
{
    if(nod == T[nod])
        return nod;
    T[nod] = getRoot(T[nod]);
    return T[nod];
}