#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define pii pair<int, int>

using namespace std;

const int NMAX = 2e5 + 5;
const int MMAX = 4e5 + 5;
const int INF = 1e9 + 7;
const char nl = '\n';

vector<pii> g[NMAX], tree;
bool visited[NMAX];
int min_cost[NMAX], father[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

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

    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    for(int i = 1; i <= n; ++i) {
        min_cost[i] = INF;
    }

    int cost = 0;
    min_cost[1] = 0;

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, 1}); // weight and node

    while(!pq.empty()) {
        int weight = pq.top().first;
        int node = pq.top().second;
        pq.pop();

        if(visited[node]) {
            continue;
        }

        visited[node] = true;
        cost += weight;
        
        if(father[node] != 0) {
            tree.push_back({father[node], node});
        }


        for(auto neigh: g[node]) {
            int neigh_node = neigh.first;
            int neigh_weight = neigh.second;

            if(!visited[neigh_node] && neigh_weight < min_cost[neigh_node]) {
                min_cost[neigh_node] = neigh_weight;
                father[neigh_node] = node;
                pq.push({min_cost[neigh_node], neigh_node});
            }
        }
    }

    cout << cost << nl << tree.size() << nl;
    for(auto x: tree) {
        cout << x.second << ' ' << x.first << nl;
    }
    return 0;
}