//Prim's Algorithm  O(N^2)

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

using namespace std;

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

#define MAXN 20050
#define MAXM 40050

int EdgeCost[MAXN][MAXN];
int used[MAXN], solution[MAXN], minimal_cost[MAXN];

int N, M;

int main ()
{
    fin >>N >>M;
    for (int i = 0; i <= N+1; ++i)
        for (int j = 0; j <= N+1; ++j)
            if (i!=j)
                EdgeCost[i][j] = 99999;
    for (int i = 0 ; i < M; ++i)
    {
        int x, y, cost;
        fin >>x >>y >>cost;
        EdgeCost[x][y] = EdgeCost[y][x] = cost;
    }
    int startNode = 3;
    for (int i = 1; i <= N; ++i)
    {
        minimal_cost[i] = EdgeCost[startNode][i];
        solution[i] = startNode;
        used[i] = 1;
    }
    used[startNode] = 0;
    solution[startNode] = 0;
    int current  = N-1;
    int minimal_vertex = 0;
    while (current)
    {
        int temp_cost = 999999;
        for (int i = 1; i <= N; ++i)
            if (used[i] && temp_cost > minimal_cost[i])
            {
                temp_cost = minimal_cost[i];
                minimal_vertex = i;
            }
        used[minimal_vertex] = 1;
        --current;
        used[minimal_vertex] = 0;
        for (int i = 1; i <= N; ++i)
            if (used[i] && EdgeCost[i][minimal_vertex] < minimal_cost[i])
            {
                solution[i] = minimal_vertex;
                minimal_cost[i] = EdgeCost[i][minimal_vertex];
            }
    }
    int cost = 0;
    for (int i = 1; i <= N; ++i)
        cost+= EdgeCost[i][solution[i]];
    fout <<cost-99999 <<'\n';
    for (int i = 1; i <= N; ++i)
        fout <<i <<' ' <<solution[i] <<'\n';
    return 0;
}