// PRIM - O(mlogn)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

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

#define NMAX 200000

std::vector<std::pair<int, int>> adj[NMAX + 1];
std::vector<int> muchii;

std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;

int d[NMAX + 1], t[NMAX + 1], viz[NMAX + 1];
int n, m, sol;

void read()
{
    f >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int x, y, z;

        f >> x >> y >> z;

        adj[x].push_back(std::make_pair(y, z));
        adj[y].push_back(std::make_pair(x, z));
    }
}

void init()
{
    // initializam cu infinit
    for (int i = 1; i <= n; i++)
        d[i] = 1e9;
}

void Prim(int x)
{

    sol = d[x] = 0;

    // pg de forma (cost,nod)
    pq.push(std::make_pair(d[x], x));

    while (!pq.empty())
    {
        int x = pq.top().second;

        pq.pop();

        if (viz[x])
            continue;

        viz[x] = 1;
        sol += d[x];

        for (auto nextNode : adj[x])
        {
            // daca nodul nu e in APM si totodata costul este minim pentru acel nod
            if (!viz[nextNode.first] && d[nextNode.first] > nextNode.second)
            {
                d[nextNode.first] = nextNode.second;

                t[nextNode.first] = x;

                pq.push(std::make_pair(d[nextNode.first], nextNode.first));
            }
        }
    }
}

void print()
{
    g << sol << '\n'
      << n - 1 << '\n';

    for (int i = 2; i <= n; i++)
        g << t[i] << " " << i << '\n';
}

int main()
{
    read();

    init();

    Prim(1);

    print();

    return 0;
}