#include <iostream>
#include <climits>
#include <fstream>
#define VMAX 10000

using namespace std;

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

int W[VMAX][VMAX];
int V, E, x, y, cost;
int key[VMAX], parent[VMAX];
bool inMST[VMAX];

int extragMin()
{
    int min_index = -1;

    for (int i = 0; i < V; ++i)
        if (!inMST[i] && (min_index == -1 || key[i] < key[min_index]))
        min_index = i;

    if (key[min_index] == INT_MAX)
    {
        fout << "No MST";
        return -1;
    }

    return min_index;
}

int main()
{
   /* fin >> V;

    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
    {
        fin >> W[i][j];
        if (!W[i][j] && i != j) W[i][j] = INT_MAX;
    }
*/

    fin >> V >> E;

    while (E--)
    {
        fin >> x >> y >> cost;
        W[x - 1][y - 1] = W[y - 1][x - 1] = cost;
    }

    for (int i = 0; i < V; ++i)
        for (int j = 0; j < V; ++j)
        if (i != j && !W[i][j]) W[i][j] = INT_MAX;

    for (int i = 0; i < V; ++i)
        inMST[i] = false, parent[i] = -1, key[i] = INT_MAX;

    int total_weight = 0;
    key[0] = 0;

    for (int contor = 0; contor < V; ++contor)
    {
        int u = extragMin();

        inMST[u] = true;
        total_weight += key[u];

        for (int v = 0; v < V; ++v)
            if (W[u][v] < key[v] && !inMST[v])
            key[v] = W[u][v], parent[v] = u;
    }

    fout << total_weight << endl << V - 1 << endl;

    for (int i = 1; i < V; ++i)
        fout << parent[i] + 1 << " " << i + 1 << endl;

    fin.close();
    fout.close();
    return 0;
}

/*
5
0 2 0 6 0
2 0 3 8 5
0 3 0 0 7
6 8 0 0 9
0 5 7 9 0
*/