#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define NMAX 200010

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");


int X[NMAX], Y[NMAX], C[NMAX], t[NMAX], ind[NMAX];
int cost;
vector <int> v;

int componenta_conexa(int nod)
{
    if(t[nod] == nod)
        return nod;
    t[nod] = componenta_conexa(t[nod]);
    return t[nod];
}

void reuniune(int i, int j)
{
    t[componenta_conexa(i)] = componenta_conexa(j);
}

bool sortare(int x, int y)
{
    return (C[x] < C[y]);
}

int main()
{
    int N, M, i;
    f >> N >> M;
    for(i = 1; i <= M; i++)
    {
        f >> X[i] >> Y[i] >> C[i];
        ind[i] = i;
        t[i] = i;
    }
    sort(ind+1, ind+M+1, sortare);
    for(i = 1; i <= M; i++)
    {
        if(componenta_conexa(X[ind[i]]) != componenta_conexa(Y[ind[i]]))
        {
            cost += C[ind[i]];
            reuniune(X[ind[i]], Y[ind[i]]);
            v.push_back(ind[i]);
        }
    }
    g << cost << endl <<N-1 <<endl;
    for(unsigned i = 0; i < v.size(); i++)
        g<<X[v[i]]<<" "<<Y[v[i]]<<endl;
    return 0;
}