#include <bits/stdc++.h>

using namespace std;

const int Nmax = 200000 + 1;
const int Mmax = 400000 + 1;
const int INF = 2e9;

struct Node
{
    int nod;
    int val;

    bool operator < (const Node& A) const
    {
        return val > A.val;
    }
};

struct Edge
{
    int nod;
    int urm;
    int cost;
};

Edge G[2 * Mmax];
priority_queue<Node> MinHeap;

int dist[Nmax];
int dad[Nmax];
int head[Nmax];
bool inHeap[Nmax];

int N, M, contor;

void addEdge(int x, int y, int c)
{
    contor++;
    G[contor].nod = y;
    G[contor].cost = c;
    G[contor].urm = head[x];
    head[x] = contor;
}

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");

    ios_base::sync_with_stdio(false);

    in >> N >> M;

    for ( int i = 1; i <= M; ++i )
    {
        int a, b, c;
        in >> a >> b >> c;

        addEdge(a, b, c);
        addEdge(b, a, c);
    }

    for ( int i = 1; i <= N; ++i )
        dist[i] = INF;

    dist[1] = 0;
    dad[1] = 0;
    MinHeap.push({1, 0});
    int costAPM = 0;

    for ( int i = 1; i <= N; ++i )
    {
        while ( MinHeap.size() && dist[ MinHeap.top().nod ] != MinHeap.top().val )
            MinHeap.pop();

        int nod = MinHeap.top().nod;
        costAPM += dist[nod];
        inHeap[nod] = true;
        MinHeap.pop();

        for ( int p = head[nod]; p; p = G[p].urm )
        {
            int son = G[p].nod;
            int cost = G[p].cost;

            if ( dist[son] > cost && inHeap[son] == false )
            {
                dad[son] = nod;
                dist[son] = cost;
                MinHeap.push({son, dist[son]});
            }
        }
    }

    out << costAPM << "\n";
    out << N - 1 << "\n";

    for ( int i = 2; i <= N; ++i )
        out << i << " " << dad[i] << "\n";

    return 0;
}