/*
D[i] = inf , 1<=i<=n
D[1]=0
pq push({D[1], 1})
while pq not empty do
    cost = pq.top().first
    nod = pq.top().second
    if viz[nod] == 1 then continue
    viz[nod] = 1
    sol+=cost
    for each vecin v of nod do
       if d[v] > cost_muchie(nod, v)
            d[v] = cost_muchie(nod, v)
            pq push({d[v], v})
            p(v) = nod
print sol
for i = 1 to n do
   print(i, p(i))


L[v] ={(y,cost)
O(m log n)
 */

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

const int MAXN = 200005;
const int INF = INT_MAX;

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


vector<pair<int, int>> L[MAXN];
int D[MAXN];
int p[MAXN];
bool viz[MAXN];

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

    int N, M;
    fin >> N >> M;

    for (int i = 0; i < M; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        L[x].push_back({y, c});
        L[y].push_back({x, c});
    }

    for (int i = 1; i <= N; i++) {
        D[i] = INF;
        p[i] = 0;
        viz[i] = false;
    }

    D[1] = 0;

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({D[1], 1});

    long long sol = 0;
    int muchii_count = 0;

    while (!pq.empty()) {
        int cost = pq.top().cost;
        int nod = pq.top().nod;
        pq.pop();


        if (viz[nod] == 1) continue;

        viz[nod] = 1;

        sol += cost;
        muchii_count++;


        for (auto it : L[nod]) {
            int v = it.first;
            int cost_muchie = it.second;

            if (D[v] > cost_muchie) {
                D[v] = cost_muchie;
                pq.push({D[v], v});
                p[v] = nod;
            }
        }
    }


    fout << sol << "\n";
    fout << muchii_count - 1 << "\n";

    for (int i = 1; i <= N; i++) {
        if (p[i] != 0) {
            fout << i << " " << p[i] << "\n";
        }
    }

    fin.close();
    fout.close();

    return 0;
}