#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int INF = 0x3f3f3f3f;

struct HeapState
{
    int nod, cost;
    bool operator < (const HeapState& other) const
    {
        return cost > other.cost;
    }
};

int n, m, costmax, viz[200001], t[200001];
vector <int> dist;
vector < pair <int, int> > graf[200001];
priority_queue <HeapState> pq;

void citire()
{
    f>>n>>m;
    int x, y, cost;
    for (int i = 1; i <= m; ++i)
    {
        f>>x>>y>>cost;
        graf[x].push_back({y, cost});
        graf[y].push_back({x, cost});
    }
    dist = vector <int> (n+1, INF);
}

void un_apm()
{
    dist[1] = 0;
    pq.push({1, 0});

    while (!pq.empty())
    {
        int nod = pq.top().nod;
        int cost = pq.top().cost;
        pq.pop();
        if (!viz[nod])
        {
            viz[nod] = 1;
            costmax += cost;
            for (auto muchie: graf[nod])
            {
                int nodnou = muchie.first;
                int costnou = muchie.second;
                if (!viz[nodnou] && costnou < dist[nodnou])
                {
                    pq.push({nodnou, costnou});
                    dist[nodnou] = costnou;
                    t[nodnou] = nod;
                }
            }
        }
    }
}

void afisare()
{
    g << costmax << '\n';
    g << n - 1 << '\n';
    for (int i = 2; i <= n; ++i)
        g << i << ' ' << t[i] << '\n';
    g << '\n';
}

int main()
{
    citire();
    un_apm();
    afisare();

    f.close();
    g.close();
    return 0;
}