#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
vector<vector<pair<int,int>>> adj;
void citire(){
    fin >> n >> m;
    adj.resize(n+1);
    while(m--){
        int x,y,c;
        fin >> x >> y >> c;
        adj[x].push_back({y, c});
        adj[y].push_back({x,c});
    }
}
void prim(int start){
    priority_queue<tuple<int,int,int>, vector<tuple<int,int,int>>, greater<>> pq;
    vector<bool> viz(n+1, 0);
    vector<int> parent(n+1, -1);
    int ans = 0;
    pq.push({0, start, -1});
    while(!pq.empty()){
        auto [wt, u, par] = pq.top();
        pq.pop();
        
        if(viz[u]) continue;
        viz[u] = 1;
        ans += wt;
        parent[u] = par;
        for(auto v : adj[u]){
            if(!viz[v.first]){
                pq.push({v.second, v.first,  u});
            }
        }
    }
    fout << ans << '\n' << n-1 << '\n';
    for(int i = 1; i<=n; i++){
        if(parent[i] != -1) fout << parent[i] << ' ' << i << '\n';
    }
}
int main(){
    citire();
    prim(1);

    return 0;
}