#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
#include <functional>
#define NMAX 200003
#define oo (1 << 30)

using namespace std;

vector<pair<int, int> > G[NMAX];
int n;
int d[NMAX], father[NMAX];

struct compare{

    bool operator() (const pair<int,int>& f, const pair<int, int>& s) {

        if (f.first <= s.first)
            return false;
        return true;
    }
};

priority_queue <pair<int,int>, vector<pair<int, int> >, compare > heap;
bitset<NMAX> mark;

void read() {

    ifstream in("apm.in");
    int m, x, y, z;
    in >> n >> m;

    for (int i = 1; i <= m; i++) {

        in >> x >> y >> z;
        G[x].push_back(make_pair(y, z));
        G[y].push_back(make_pair(x, z));
    }
    in.close();
}

void apm() {

    int node, where, cost;
    heap.push(make_pair(0, 1));

    mark.set(1);

    for (int i = 2; i <= n; i++)
        d[i] = oo;

    while (!heap.empty()) {

        node = heap.top().second;
        heap.pop();
        mark.set(node);

        for (unsigned int i = 0; i < G[node].size(); i++)
        {
            where = G[node][i].first;
            cost = G[node][i].second;

            if (!mark.test(where) && d[where] > cost)
            {

                d[where] = cost;
                father[where] = node;
                heap.push(make_pair(d[where], where));

            }
        }
    }
}

int main()
{
    read();
    apm();

    long long int cost = 0;

    for (int i = 1; i <= n; i++)
        cost += (d[i] * 1LL);

    ofstream out("apm.out");
    out << cost << "\n";
    out << n - 1 << "\n";

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

    out.close();
    return 0;
}