//Prim O(m logn)
#include <bits/stdc++.h>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n,m;
vector < pair <int, int> > G[200005];
set < pair <int,int> > s;
int d[200005];
int t[200005];
bool viz[200005];
void prim(){
    int rez = 0;
    d[1] = 0;
    t[1] = 1;
    s.insert({d[1],1});
    while(!s.empty()){
        auto it = s.begin();
        int dist = it->first;
        int nod = it->second;
        s.erase(it);
        if(viz[nod]) continue;
        viz[nod] = 1;
        rez += dist;
        for(auto x : G[nod]){
            int v = x.second;
            int c = x.first;
            if(!viz[v] && d[v] > c){
                d[v] = c;
                s.insert({d[v],v});
                t[v] = nod;
            }
        }
    }
    fout << rez << "\n" << n - 1 << "\n";
    for(int i = 2; i <= n; i++) fout << t[i] << " " << i << "\n";
}
int main()
{
    int u,v,c;
    fin >> n >> m;
    for(int i = 1; i <= n; i++) d[i] = 1e9;
    for(int i = 1; i <= m; i++){
        fin >> u >> v >> c;
        G[u].push_back({c,v});
        G[v].push_back({c,u});
    }
    prim();
    return 0;
}