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

using namespace std;

const int N = 100001;
const int INF = 1000000000;

struct muchie {
    int vf, cst;
};

int n, m;
bool sel[N];
vector <muchie> a[N];
priority_queue <pair<int, int>, vector <pair<int, int> >, greater <pair <int, int> > > h;
int d[N], pred[N], cost;

void citire() {
    int x, y, c;
    ifstream in("apm.in");
    in >> n >> m;
    for (int i = 0; i < m; i++) {
        in >> x >> y >> c;
        a[x].push_back((muchie){y, c});
        a[y].push_back((muchie){x, c});
    }
    in.close();
}

void dijkstra(int x0) {
    int x, y, c;
    //initializari
    d[x0] = 0;
    h.push(make_pair(d[x0], x0));//adaug in heap vf initial cu dist 0
    for (int i = 2; i <= n; i++) { //celelalte varfuri cu distanta INF
        d[i] = INF;
        h.push(make_pair(d[i], i));//le pun cu minus pt ca priority_queue face implicit maxHeap
    }
    while (!h.empty()) {
        //extrag varful neselectat anterior cu distanta minima
        while (!h.empty() && sel[h.top().second]) {
            h.pop();
        }
        if (!h.empty()) {
            //am gasit un varf neselectat
            x = h.top().second;
            sel[x] = true;
            cost += d[x];
            for (int i = 0; i < a[x].size(); i++) {
                y = a[x][i].vf;
                c = a[x][i].cst;
                if (c < d[y] && !sel[y]) {
                    d[y] = c;
                    pred[y] = x;
                    h.push(make_pair(d[y], y));
                }
            }
        }
    }
}

void afisare() {
    ofstream out("apm.out");
    out << cost << "\n" << n - 1 << "\n";
    for (int i = 2; i <= n; i++) {
        //out << (d[i] == INF ? 0 : d[i]) << " ";
        out << pred[i] << " " << i << "\n";
    }
    out.close();
}

int main() {
    citire();
    dijkstra(1);
    afisare();
    return 0;
}