#include <iostream>
#include <vector>
#include <bits/stdc++.h>
#include <fstream>
#include <utility>
#include <climits>

using namespace std;

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

int n, m, x, y, cost, nod, viz[10000001], sol, c, d[1000005], p[1000005];
priority_queue<pair<int, int>> PQ;
vector <pair<int, int>> L[10000001];
vector <pair<int, int>> muchii;


int main() {
    for(auto i: p)
        p[i] = 0;
    fin >> n >> m;
    for (int i = 1; i <= n; i++) {
        d[i] = INT_MAX;
    }
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        L[x].push_back({y, c});
        L[y].push_back({x, c});
    }
    d[1] = 0;
    PQ.push({0, 1});
    while (PQ.size() > 0) {
        cost = PQ.top().first;
        nod = PQ.top().second;
        PQ.pop();
        if (viz[nod]) continue;
            viz[nod] = 1;
            sol += cost;
            if (nod != 1)
                muchii.push_back({nod, p[nod]});
            for (auto m : L[nod]) {
                if (d[m.first] > m.second && !viz[m.first]) {
                    d[m.first] = m.second;
                    PQ.push({-d[m.first], m.first});
                    p[m.first] = nod;
                }
            }
    }
    fout << (-1)*sol << '\n' << muchii.size() << "\n";
    for (auto m : muchii) {
        fout << m.first << ' ' << m.second << '\n';
    }
}