#include <iostream>
#include <vector>
#include <fstream>
#include <limits>
#include <tuple>

using namespace std;

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

struct Muchie
{
    int x;
    int y;
    int cost = 0;
};

int Parent(int i)
{
    return i / 2;
}
int Left(int i) { return 2 * i; }
int Right(int i) { return 2 * i + 1; }

int d[200001];

void minHeapInsert(int heap[], int &size, int x)
{
    int i = size + 1;
    size += 1;
    heap[i] = x;
    while (i != 1 && d[heap[i]] < d[heap[i / 2]])
    {
        swap(heap[i], heap[i / 2]);
        i /= 2;
    }
}

void minHeapify(int heap[], int size, int pos)
{
    int left = pos * 2;
    int right = pos * 2 + 1;
    int smallest;
    if (left <= size and d[heap[left]] < d[heap[pos]])
        smallest = left;
    else
        smallest = pos;
    if (right <= size and d[heap[right]] < d[heap[smallest]])
        smallest = right;
    if (smallest != pos)
    {
        swap(heap[pos], heap[smallest]);
        minHeapify(heap, size, smallest);
    }
}

int extractMin(int heap[], int &size)
{
    int minimum = heap[1];
    heap[1] = heap[size];
    size -= 1;
    minHeapify(heap, size, 1);
    return minimum;
}

void createMinHeap(int heap[], int size)
{
    for (int i = size / 2; i > 0; i--)
        minHeapify(heap, size, i);
}

bool inQ(int Q[], int size, int elem)
{
    for (int i = 1; i <= size; i++)
        if (Q[i] == elem)
            return true;
    return false;
}

void Prim()
{
    int n, m;
    in >> n >> m;
    vector<vector<tuple<int, int>>> listaAdiacenta;
    listaAdiacenta.resize(n + 1);
    for (int i = 1; i <= m; i++)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        listaAdiacenta[x].push_back(make_tuple(y, cost));
        listaAdiacenta[y].push_back(make_tuple(x, cost));
    }

    // for (int i = 1; i <= n; i++)
    // {
    //     cout << i << ": ";
    //     for (int j = 0; j < listaAdiacenta[i].size(); j++)
    //     {
    //         cout << "( " << get<0>(listaAdiacenta[i][j]) << ", " << get<1>(listaAdiacenta[i][j]) << " ), ";
    //     }
    //     cout << endl;
    // }

    int tata[n + 1];
    int radacina = 1;
    int infinity = numeric_limits<int>::max();
    for (int i = 1; i <= n; i++)
    {
        d[i] = infinity;
        tata[i] = 0;
    }
    d[radacina] = 0;
    int Q[n + 1];
    for (int i = 1; i <= n; i++)
        Q[i] = i;
    int size = n;
    createMinHeap(Q, size);
    while (size != 0)
    {
        int u = extractMin(Q, size);
        // cout << u << ": ";
        // for (int i = 1; i <= size; i++)
        //     cout << Q[i] << " ";
        // cout << endl;
        for (auto it : listaAdiacenta[u])
        {
            int v = get<0>(it);
            int cost = get<1>(it);
            if (inQ(Q, size, v) == true && cost < d[v])
            {
                d[v] = cost;
                tata[v] = u;
                minHeapify(Q, size, v);
            }
        }
    }
    int costTotal = 0;
    for (int i = 1; i <= n; i++)
    {
        costTotal += d[i];
    }
    out << costTotal << endl;
    out << n - 1 << endl;
    for (int i = 2; i <= n; i++)
    {
        out << i << " " << tata[i] << endl;
    }
}

int main()
{
    Prim();
    return 0;
}

// void minHeapInsert(vector<Muchie> &heap, Muchie muchie)
// {
//     heap.push_back(muchie);
//     int i = heap.size() - 1;
//     while (i != 1 && heap[i].cost < heap[i / 2].cost)
//     {
//         swap(heap[i], heap[i / 2]);
//         i /= 2;
//     }
// }

// void minHeapify(vector<Muchie> &heap, int pos)
// {
//     int left = pos * 2;
//     int right = pos * 2 + 1;
//     int size = heap.size() - 1;
//     int smallest;
//     if (left <= size and heap[left].cost < heap[pos].cost)
//         smallest = left;
//     else
//         smallest = pos;
//     if (right <= size and heap[right].cost < heap[smallest].cost)
//         smallest = right;
//     if (smallest != pos)
//     {
//         swap(heap[pos], heap[smallest]);
//         minHeapify(heap, smallest);
//     }
// }

// Muchie extractMin(vector<Muchie> &heap)
// {
//     Muchie minimum = heap[1];
//     heap[1] = heap[heap.size() - 1];
//     heap.pop_back();
//     minHeapify(heap, 1);
//     return minimum;
// }

// void createMinHeap(vector<Muchie> &heap)
// {
//     for (int i = heap.size() / 2; i > 0; i--)
//         minHeapify(heap, i);
// }

// void printHeap(vector<Muchie> heap)
// {
//     for (int i = 1; i < heap.size(); i++)
//         out << heap[i].x << " " << heap[i].y << " " << heap[i].cost << endl;
//     out << '\n';
// }