#include <bits/stdc++.h>
#define PII pair < int , int >

using namespace std;

int n, m, apm, dad[200005], dist[200005];
vector < PII > V[200005];
set < PII > S;
bitset < 200005 > B;

int main(){
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;

    for (int i = 1; i <= n; i++) dist[i] = 2e9;

    for (int i = 1, x, y, z; i <= m; i++){
        cin >> x >> y >> z;
        V[x].push_back({y, z});
        V[y].push_back({x, z});
    }

    S.insert({0, 1}); // first - weight, second - node
    dist[1] = 0;

    while (S.size()){
        apm += S.begin()->first;

        int node = S.begin()->second;
        S.erase(S.begin());
        B[node] = 1;

        for (auto it : V[node]){
            int vertex = it.first;
            int weight = it.second;

            if (!B[vertex] && weight < dist[vertex]){
                if (dist[vertex] != 2e9)
                    S.erase(S.find({dist[vertex], vertex}));

                dist[vertex] = weight;
                dad[vertex] = node;
                S.insert({dist[vertex], vertex});
            }
        } 
    }

    cout << apm << "\n" << n - 1 << "\n";
    for (int i = 1; i <= n; i++){
        if (dad[i] != 0)
            cout << dad[i] << " " << i << "\n";
    }

    return 0;
}