#include <fstream>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

typedef pair<int, int> iPair;
const int DIM = 200010;
const int INF = 1001;
struct edge {
    int node, cost;
};

int n, m, x, y, c;
vector<edge> l[DIM];
int cost[DIM], father[DIM];
bool inMST[DIM];
priority_queue<iPair, vector<iPair>, greater<iPair>> pq;

int main() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        fin >> x >> y >> c;
        l[x].push_back({ y, c });
        l[y].push_back({ x, c });
    }

    for (int i = 1; i <= n; i++)
        cost[i] = INF;

    int minCost = 0;
    cost[1] = father[1] = 0;
    pq.push(make_pair(0, 1));
    while (!pq.empty()) {
        int node = pq.top().second;
        pq.pop();
        if (inMST[node]) continue;

        inMST[node] = true;
        minCost += cost[node];
        for (int i = 0; i < l[node].size(); i++) {
            int adjNode = l[node][i].node;
            int adjCost = l[node][i].cost;
            if (!inMST[adjNode] && cost[adjNode] > adjCost) {
                father[adjNode] = node;
                cost[adjNode] = adjCost;
                pq.push(make_pair(cost[adjNode], adjNode));
            }
        }
    }

    fout << minCost << '\n' << n - 1 << '\n';
    for (int i = 2; i <= n; i++)
        fout << i << ' ' << father[i] << '\n';

    return 0;
}