#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 1002;
const int oo = 1e8;

int G[Nmax][Nmax];
bool use[Nmax][Nmax];
bool selected[Nmax];
int cmin[Nmax];
int tata[Nmax];

int N, M, R;

void read()
{
    ifstream f("apm.in");

    f >> N >> M;

    for ( int i = 1; i <= N; ++i )
            for ( int j = 1; j <= N; ++j )
                    G[i][j] = oo;

    for ( int i = 1; i <= M; ++i )
    {
        int a, b;
        int c;

        f >> a >> b >> c;

        G[a][b] = G[b][a] = c;
    }

    f.close();
}

void init()
{
    R = 1;

    cmin[R] = -oo;
    tata[R] = 0;

    for ( int i = 2; i <= N; ++i )
    {
        cmin[i] = G[R][i];
        tata[i] = R;
    }
}

void MST()
{
    int sel = N, cost_min, vertex;

    while( sel-- )
    {
        cost_min = oo;

        for ( int i = 1; i <= N; ++i )
                if ( !selected[i] && cost_min > cmin[i] )
                {
                    vertex = i;
                    cost_min = cmin[i];
                }

        selected[vertex] = 1;

        for ( int i = 1; i <= N; ++i )
                if ( !selected[i] && cmin[i] > G[vertex][i] )
                {
                    tata[i] = vertex;
                    cmin[i] = G[vertex][i];
                }
    }
}

void print()
{
    ofstream g("apm.out");

    int cost = 0;

    for ( int i = 1; i <= N; ++i )
            if ( i != R )
            {
                cost += G[i][ tata[i] ];
            }

    g << cost << "\n";
    g << N - 1 << "\n";

    for ( int i = 1; i <= N; ++i )
            if ( i != R )
            {
                g << i << " " << tata[i] << endl;
            }

    g.close();
}


int main()
{
    read();
    init();
    MST();
    print();

    return 0;
}