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


using namespace std;

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

vector<pair<int, int> > sol;
vector<vector<pair<int, int> > > vec;
int viz[20005], d[20005], tata[20005], n, m;
pair<int, int> minim_path(){
    pair<int, int> p = make_pair(1e9, 0);
    for(int i=1; i<=n; i++){
        if(viz[i] == 0 and d[i] < p.first){
            p.first = d[i];
            p.second = i;
        }
    }
    return p;
}

void prim(int s, int &cost){
    for(int i=1; i<=n; i++){
        d[i] = 1e9;
        viz[i] = 0;
        tata[i] = 0;
    }
    d[s] = 0;

    for(int k=0; k<n; k++){
        pair<int, int> p = minim_path();
        viz[p.second] = 1;

        for(auto nod : vec[p.second]){
            int vf = nod.first;
            int cost = nod.second;

            if(viz[vf] == 0 and d[vf] > cost){
                d[vf] = cost;
                tata[vf] = p.second;
            }
        }
}
    for(int i=1; i<=n; i++){
        if(tata[i]!=0){
            sol.push_back(make_pair(tata[i], i));
            cost += d[i];
        }
    }
}



int main(){
    fin>>n>>m;
    vec.resize(n+5);
    for(int i=1; i<=m; i++){
        int x, y, z;
        fin>>x>>y>>z;
        vec[x].push_back(make_pair(y, z));
        vec[y].push_back(make_pair(x, z));
    }
    int cost = 0;
    prim(1, cost);
    fout<<cost<<endl;
    fout<<n-1<<endl;
    for(int i=0; i< sol.size(); i++){
        fout<<sol[i].first<<' '<<sol[i].second<<endl;
    }
    return 0;
}