#include <bits/stdc++.h>
using namespace std;

struct edge {
    int node, cost, t;
};

struct comp {
    bool operator()(edge a, edge b) {
        return a.cost > b.cost;
    }
};

int n, m;
vector<vector<pair<int, int>>> v(200001);
priority_queue<edge, vector<edge>, comp> q;
bool vis[200001];

int main() {
    ifstream cin("apm.in");
    ofstream cout("apm.out");
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int c, x, y;
        cin >> x >> y >> c;
        v[x].push_back({y, c});
        v[y].push_back({x, c});
    }
    q.push({1, 0});
    vector<pair<int, int>> edges;
    int totalCost = 0;
    while (!q.empty()) {
        int node = q.top().node;
        int nodeCost = q.top().cost;
        int father = q.top().t;
        q.pop();
        if (!vis[node]) {
            if (node != 1) {
                totalCost += nodeCost;
                edges.push_back({father, node});
            }
            for (int i = 0; i < v[node].size(); ++i) {
                q.push({v[node][i].first, v[node][i].second, node});
            }
        }
        vis[node] = true;
    }
    cout << totalCost << "\n" << edges.size() << "\n";
    for (int i = 0; i < edges.size(); ++i) {
        cout << edges[i].first << " " << edges[i].second << "\n";
    }
}