#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

constexpr int NMAX = 1005;

int Mat[NMAX][NMAX];

int N, M;
int sol[NMAX];
int ind[NMAX];
pair <int, int> muchii[NMAX];

bool viz[NMAX];

void Initialize () {
    for (int i = 0; i <= N; ++ i )
        viz[i] = 0, sol[i] = INF;

    for (int i = 1; i <= N; ++ i )
        for (int j = 1; j <= N; ++ j )
            Mat[i][j] = INF;
}

void Read () {
    f >> N >> M;

    Initialize();

    for (int i = 1; i <= M; ++ i ) {
        int x, y, c;
        f >> x >> y >> c;

        Mat[x][y] = Mat[y][x] = c;
    }
}

void Solve () {
    sol[1] = 0;
    ind[1] = 0;

    for (int i = 1; i <= N; ++ i ) {
        int node = 0;
        for (int j = 1; j <= N; ++ j ) {
            if (viz[j]) continue;

            if (sol[node] > sol[j]) node = j;
        }

        muchii[i] = {ind[node], node};
        viz[node] = 1;

        for (int j = 1; j <= N; ++ j ) {
            if (viz[j]) continue;

            if (sol[j] > Mat[node][j]) {
                sol[j] = Mat[node][j];
                ind[j] = node;
            }
        }
    }

    int cost = 0;
    for (int i = 1; i <= N; ++ i )
        cost += sol[i];

    g << cost << '\n' << N-1 << '\n';
    for (int i = 2; i <= N; ++ i )
        g << muchii[i].first << " " << muchii[i].second << '\n';
}

int main()
{
    Read ();

    Solve();

    return 0;
}