#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

const int NMAX = 400100;

int GR[NMAX],X[NMAX],Y[NMAX],C[NMAX];
int n,m,ANS,IND[NMAX];

vector <int> VANS;

bool cmpf(int i, int j); /// criteriu de sortare
int grupa(int i);
void reuniune(int i, int j);

int main()
{
    fin >> n >> m; /// noduri si muchii

    for(int i = 1; i <= m; i++)
    {
        fin >> X[i] >> Y[i] >> C[i]; /// muchia (x;y) cu costul C
        IND[i] = i; /// indicele
    }

    for(int i = 1; i <= n; i++)
        GR[i] = i; /// initializam componentele conexe

    sort(IND + 1, IND + m + 1, cmpf);

    for(int i = 1; i <= m; i++)
    {
        if(grupa(X[ IND[i] ]) != grupa(Y[ IND[i] ]) )
        {
            ANS += C[ IND[i] ];
            reuniune( X[ IND[i] ], Y[ IND[i] ] );
            VANS.pb(IND[i]);

        }
    }

    fout << ANS << "\n";
    fout << n-1 << "\n";
    for(int i = 0; i < n-1; ++i)
        fout << Y[ VANS[i] ] << " " << X[ VANS[i] ] << "\n";

    return 0;
}

bool cmpf(int i, int j)
{
    return (C[i] < C[j]); /// sorteaza muchiile in functie de costuri
}

int grupa(int i)
{
    if(GR[i] == i)
        return i;
    GR[i] = grupa(GR[i]);
    return GR[i];
}

void reuniune(int i, int j)
{
    GR[grupa(i)] = grupa(j);
}