#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
struct muchie
{
    int i,j,cost;
}x[400005];

//muchie x[5000];
int t[200005];

bool sortfunc(muchie a,muchie b)
{
    return (a.cost < b.cost);
}
int main()
{
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    int n, m;
    vector<muchie> vres;
    cin >> n >> m;

    for(int i = 0 ; i < m ; ++i)
        cin >> x[i].i >> x[i].j >> x[i].cost;

    sort(x,x+m,sortfunc);
    for(int i =1 ; i <= n ; ++i)
        t[i] = i;

    int S = 0;
    for(int i = 0 ; i < m ; i ++)
    {
        if(t[x[i].i] != t[x[i].j])
        {
            vres.push_back(x[i]);
            S += x[i].cost;
            int ai = t[x[i].i], aj = t[x[i].j];
            for(int j =1 ; j <= n ; ++j)
                if(t[j] == aj)
                    t[j] = ai;
        }
    }
    cout << S << endl << n-1 << endl;
    for(auto k : vres)
    {
        cout << k.j << " " << k.i << endl;
    }
    return 0;
}