#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
const int inf = 1e9;

vector<pair<int, int>> L[1000001];

int p[1000001];
int h[1000001];
int d[1000001];
int viz[1000001];
int parent[1000001];

priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

struct Muchie {
    int x;
    int y;
    int c;
};

int find(int x) {
    while (x != p[x]) {
        x = p[x];
    }
    return x;
}

void unionn(int x, int y){
    x = find(x);
    y = find(y);
    if(h[x] < h[y]){
        p[x] = y;
    }
    else if (h[x] > h[y]){
        p[y] = x;
    }
    else{
        p[x] = y;
        h[y]++;
    }
}

int main() {
    int n, m, sol = 0, nrmuchii = 0, nod;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        p[i] = i;
        h[i] = 0;
        d[i] = inf;
        viz[i] = 0;
        parent[i] = 0;
    }

    vector<Muchie> edges;
    vector<Muchie> partial;
    
    vector<pair<int, int>> mst_edges;

    int x, y, c;
    for (int i = 0; i < m; i++) {
        cin >> x >> y >> c;
        edges.push_back({x, y, c});

        L[x].push_back({y,c});
        L[y].push_back({x, c});
    }

    std::sort(edges.begin(), edges.end(), [](const Muchie& a, const Muchie& b) {
        return a.c < b.c;
    });

    d[1] = 0;
    pq.push({d[1],1});

    while (!pq.empty()) {
        int cost = pq.top().first;
        int nod = pq.top().second;
        pq.pop();
        if (viz[nod] == 1) { 
            continue;
        }

        viz[nod] = 1;
        sol += cost;

        if (parent[nod] != 0) {
            mst_edges.push_back({parent[nod], nod});
        }
    
        for (auto& vec : L[nod]) {
            int vecin = vec.first;
            int cost_muchie = vec.second;

            if (viz[vecin] == 0 && cost_muchie < d[vecin]) {
                d[vecin] = cost_muchie;
                parent[vecin] = nod;
                pq.push({d[vecin], vecin});
            }
        }
    }


    // for (const auto& edge : edges){
    //     if(find(edge.x)!=find(edge.y)){
    //         sol+=edge.c;
    //         unionn(edge.x,edge.y);
    //         partial.push_back({edge.x,edge.y,edge.c});
    //         nrmuchii++;
    //         }
    // }

    // cout<<sol<<'\n'<<nrmuchii<<'\n';

    // for (const auto& edge : partial){
    //     cout<<edge.y<<' '<<edge.x<<'\n';
    // }


    cout << sol << '\n';
    cout << n - 1 << '\n';
    for (const auto& edge : mst_edges) {
        cout << edge.second << ' ' << edge.first << '\n';
    }

    return 0;
}