#include<fstream>
#include<algorithm>
#include<vector>
#define pb push_back
#define NMAX 400100

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

int X[NMAX],Y[NMAX],C[NMAX];
int N,M,p,ind[NMAX];
int t[NMAX];
vector<int> v;
int componenta_conexa(int nod)                   // det daca doua elemente sunt in aceeasi multime.
{

    if(nod=t[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 i,int j)
{
    return(C[i] < C[j]);
}

int main()
{

    f>>N>>M;
    for(int 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(int i = 1; i <= M; ++i)
    {
        if (componenta_conexa(X[ind[i]]) != componenta_conexa(Y[ind[i]]))
        {
            p+=C[ind[i]];
            reuniune(X[ind[i]],Y[ind[i]]);
            v.pb(ind[i]);
        }
    }
    g<<p;
    g<<N - 1;
    for(int i = 0; i <v.size(); ++i)
        g<<X[v[i]]<<" "<<Y[v[i]];
    return 0;
}