#include <bits/stdc++.h>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");

vector<bool> inTree;
int n, m, x, y, cost;
typedef tuple<int, int, int> tiii;
typedef pair<int, int> pii;
priority_queue<tiii, vector<tiii>, greater<tiii>> q;
vector<vector<pii>> adj;
vector<pii> sol;
int totalCost;

int main() {
    in >> n >> m;
    adj.resize(n + 1);
    inTree.resize(n + 1, false);

    while(m --) {
        in >> x >> y >> cost;
        adj[x].push_back({y, cost});
        adj[y].push_back({x, cost});
    }

    q.push({0, -1, 1});
    while(!q.empty() && sol.size() < n - 1) {
        int currCost = get<0>(q.top()), prevNode = get<1>(q.top()), currNode = get<2>(q.top());
        q.pop();
        
        if(inTree[currNode])
            continue;

        totalCost += currCost;
        if(prevNode != -1)
            sol.push_back({prevNode, currNode});
        inTree[currNode] = true;
        for(auto nextPair : adj[currNode]) {
            int nextNode = nextPair.first, nextCost = nextPair.second;
            q.push({nextCost, currNode, nextNode});
        }
    }

    out << totalCost << '\n' << sol.size() << '\n';
    for(auto pair : sol)
        out << pair.first << ' ' << pair.second << '\n';

    return 0;
}