#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

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

struct muchie{
    int u, v;
    int cost;
    bool operator< (const muchie& other) const{
        return cost < other.cost;
    }
};

vector<vector<pair<int, int>>> adj; // {cost, vecin}
vector<int> d; // dist de la sursa
vector<int> tata; 
vector<bool> viz;
void prim(int s){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    d[s] = 0;
    tata[s] = 0;
    pq.push({0, s});
    while(!pq.empty()){
        int u = pq.top().second;
        int cost = pq.top().first;
        pq.pop();
        if(viz[u] == false){
            viz[u] = true;
            for(auto perecheV : adj[u]){
                int v = perecheV.second;
                int pret = perecheV.first;
                if(d[v] > pret){
                    d[v] = pret;
                    tata[v] = u;
                    pq.push({d[v], v});
                }
            }
        }
    }
}
const int INF = 1e9;
int main(){
    int N, M;
    fin >> N >> M;
    tata.assign(N+1, -1);
    d.assign(N+1, INF);
    viz.assign(N+1, false);
    adj.assign(N+1, {});
    for(int i = 0; i < M; i++)
    {
        muchie a;
        fin >> a.u >> a.v >> a.cost;
        adj[a.u].push_back({a.cost, a.v});
        adj[a.v].push_back({a.cost, a.u});
    }
    int s = 1;
    prim(s);
    vector<pair<int, int>> apm;
    int costAPM= 0;
    for(int i = 1; i <= N; i++){
        if(i == s) continue;
        apm.push_back({i, tata[i]});
        costAPM += d[i];
    }
    fout << costAPM << endl;
    fout << apm.size() << endl;
    for(auto m : apm){
        fout << m.first << "  "<< m.second << endl;
    }
    return 0;
}