#include <fstream>
#include <vector>
#include <iostream>
#include <set>
#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::set<std::pair<int, int>> Q;
    Q.insert({0, node});
    dist[1] = 0;
    while(!Q.empty()){
        int c = Q.begin() ->first;
        int node = Q.begin() ->second;
        Q.erase(Q.begin());
        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]){
                if(Q.find({dist[it.first], it.first}) != Q.end()){
                    Q.erase(Q.find({dist[it.first], it.first}));
                }
                dist[it.first] = it.second;
                parent[it.first] = node;
                
                Q.insert({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";
    }
}