#include <fstream>
#include <vector>
#include <iostream>
#include <queue>
#define INF (1 << 30)
std::ifstream fin("apm.in");
std::ofstream fout("apm.out");
int n, m, dist[200001], viz[200001], cost;
std::vector<std::pair<int, int>> edges;
std::vector<int> parent;
std::vector<std::vector<std::pair<int, int>>> V;
void Prim(int node){
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> Q;
    Q.push({0, node});
    dist[1] = 0;
    int maxit = 0;
    while(!Q.empty() && ++maxit <= 100){
        int c = Q.top().first;
        int node = Q.top().second;
        Q.pop();
        if(viz[node] == true)
            continue;
        edges.push_back({parent[node], node});
        viz[node] = true;
        cost += c;
        
        for(std::pair<int, int> it : V[node]){
            
            if(dist[it.first] > it.second && !viz[it.first]){
                dist[it.first] = it.second;
                parent[it.first] = node;
                Q.push({dist[it.first], it.first});
            }
        }
    }
}
int main(){
    fin >> n >> m;
    int x, y, c;
    V = std::vector<std::vector<std::pair<int, int>>> (n + 1);
    parent = std::vector<int> (n + 1);
    for(int i = 1; i <= n; i++)
        dist[i] = INF;
    for(int i = 1; i <= m; i++){
        fin >> x >> y >> c;
        V[x].push_back({y, c});
        V[y].push_back({x, c});
    }
    Prim(1);
    fout << cost << "\n";
    fout << edges.size() - 1 << "\n";
    for(int i = 1; i < edges.size(); i++){
        fout << edges[i].first << " " << edges[i].second << "\n";
    }
}