/*

    algoritmul lui prim pt NlogN i think

*/
#include <bits/stdc++.h>
#define fi first 
#define se second 
using namespace std;

struct ansstrc {
    int x = 0;
    int y = 0;
    int v = 0;
};

struct erikfzf {
    int x;
    int v;
    ansstrc y;

    bool operator<(const erikfzf &a) const {
        return v > a.v;
    }
};



vector<ansstrc> dijkstra(vector<vector<pair<int, int>>> &a) {
    int n = a.size();
    priority_queue<erikfzf> pq;
    vector<ansstrc> ans;
    vector<bool> viz(n);
    pq.push({1, 0, {0, 0, 0}});
    while(!pq.empty()) {
        int x = pq.top().x;
        int v = pq.top().v;
        ansstrc tempans = pq.top().y;
        pq.pop();

        if(viz[x])
            continue;
        viz[x] = true;
        ans.push_back(tempans);
        for(auto i : a[x]) {
            if(viz[i.fi])
                continue;
            pq.push({i.fi, i.se, {x, i.fi, i.se}});
        }
    }
    return ans;
}

int main() {
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m; cin >> n >> m;

    vector<vector<pair<int, int>>> a(n);

    for(int i = 0; i < m; i ++) {
        int x, y, v; cin >> x >> y >> v; x --; y --;
        a[x].push_back({y, v});
        a[y].push_back({x, v});
    }

    vector<ansstrc> ans = dijkstra(a);

    int val = 0;
    for(auto i : ans) {
        val += i.v;
    }

    cout << val << '\n';
    cout << n - 1 << '\n';

    bool fr = true;

    for(auto i : ans) {
        if(fr) {
            fr = false;
            continue;
        }
        cout << i.x + 1 << ' ' << i.y + 1 << '\n';
    }
}