#include <fstream>
#include <vector>
#include <queue>
#include <limits>

std::ifstream in("apm.in");
std::ofstream out("apm.out");

constexpr int N = 2e5+2;

struct branch{
    int node, cost;
};
std::vector<branch> g[N];
int n, m;
int dist[N], pred[N];
bool inTree[N];

void prim(int &totalCost){
    std::fill(dist + 2, dist + 2 + n, std::numeric_limits<int>::max());
    std::priority_queue<std::pair<int, int>> heap;
    heap.push({0, 1});
    while (!heap.empty()){
        int parent = heap.top().second;
        heap.pop();
        if(inTree[parent]) continue;
        inTree[parent] = true;
        totalCost += dist[parent];
        for(auto br : g[parent]){
            int child = br.node;
            int cost = br.cost;
            if(!inTree[child] && cost < dist[child]){
                dist[child] = cost;
                pred[child] = parent;
                heap.push({-cost, child});
            }
        }
    }
    
}

int main(){
    in >> n >> m;
    for(int i=0; i<m; ++i){
        int u, v, cost;
        in >> u >> v >> cost;
        g[u].push_back({v, cost});
        g[v].push_back({u, cost});
    }
    int cost = 0;
    prim(cost);
    out << cost << '\n' << n-1 << '\n';
    for(int i=1; i<=n; ++i)
        if(pred[i]) out << i << ' ' << pred[i] << '\n';
    return 0;
}