#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <queue>
#include <utility>
#define VMAX 200000

using namespace std;

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

int V, E, x, y, cost;
vector < pair <int,int> > adj[VMAX];
int key[VMAX], parent[VMAX];
bool inMST[VMAX];

void prim()
{
    priority_queue < pair <int,int>, vector < pair <int, int> >, greater < pair <int,int > > > pq;

    pq.push(make_pair(0, 0));
    key[0] = 0;

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

        if (inMST[u] == true) continue;

        inMST[u] = true;

        for (auto w : adj[u])
        {
            int v = w.first, cost = w.second;

            if (inMST[v] == false && key[v] > cost)
            {
                key[v] = cost;
                pq.push(make_pair(key[v], v));
                parent[v] = u;
            }
        }
    }
}

int main()
{
    fin >> V >> E;

    while (E--)
    {
        fin >> x >> y >> cost;
        adj[x - 1].push_back({y - 1, cost});
        adj[y - 1].push_back({x - 1, cost});
    }

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

    prim();

    int total_weight = 0;

    for (int i = 0; i < V; ++i)
        total_weight += key[i];

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

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

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