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

using namespace std;

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

int  ACM[MAX_N];
int X[MAX_N], Y[MAX_N], C[MAX_N], R[MAX_N], Ind[MAX_N];
int cost_apm;

int comp_conexa(int a)
{
    if(R[a] == a)
        return a;
    R[a] = comp_conexa(R[a]);
    return R[a];
}

void reuniune(int a, int b)
{
    R[comp_conexa(a)] = comp_conexa(b);
}

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

int main()
{
    int N, M, i, x, y, c,nrsol=0;
    f >> N >> M;
    for(i = 1; i <= M; i++)
    {
        f >> X[i] >> Y[i] >> C[i];
        Ind[i] = i;
        R[i] = i;
    }
    sort(Ind+1, Ind+M+1, sortare);
    for(i = 1; i <= M; i++)
    {
        if(comp_conexa(X[Ind[i]]) != comp_conexa(Y[Ind[i]]))
        {
            cost_apm += C[Ind[i]];
            reuniune(X[Ind[i]], Y[Ind[i]]);
            ACM[++nrsol]=Ind[i];
        }
    }
    g << cost_apm << endl << N-1 <<endl;
    for(i = 1; i <= nrsol; i++)
        g<<X[ACM[i]]<<" "<<Y[ACM[i]]<<endl;
    return 0;
}