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

using namespace std;

unsigned int GROUP (unsigned int i);
void reunion (unsigned int i, unsigned int j);
bool compare (unsigned int i, unsigned int j);

unsigned int N, M;
unsigned int X[400001], Y[400001];
short int C[400001];

unsigned int pos[400001], group[200001];
unsigned int i;

unsigned int sol1, sol2;
vector <unsigned int> sol3;

int main ()
{
    ifstream fin ("apm.in");
    fin >> N >> M;
    for (i=1; i<=M; i++)
        fin >> X[i] >> Y[i] >> C[i];
    fin.close();
    for (i=1; i<=M; i++)
        pos[i] = i;
    for (i=1; i<=N; i++)
        group[i] = i;
    sort(pos+1,pos+M+1,compare);
    for (i=1; i<=M; i++)
        if (GROUP(X[pos[i]]) != GROUP(Y[pos[i]]))
        {
            sol1 += C[pos[i]];
            reunion(X[pos[i]],Y[pos[i]]);
            sol3.push_back(pos[i]);
        }
    sol2 = N - 1;
    ofstream fout ("apm.out");
    fout << sol1 << '\n';
    fout << sol2 << '\n';
    for (i=0; i<sol2; i++)
        fout << X[sol3[i]] << ' ' << Y[sol3[i]] << '\n';
    fout.close();
    return 0;
}

bool compare (unsigned int i, unsigned int j)
{
    return (C[i] < C[j]);
}

unsigned int GROUP (unsigned int i)
{
    if (group[i] == i)
        return i;
    group[i] = GROUP(group[i]);
    return group[i];
}

void reunion (unsigned int i, unsigned int j)
{
    group[GROUP(i)] = GROUP(j);
}