#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");
int n, m, x, y, c, total;
int h[200002], t[200002];
struct ceva{
    int cost;
    int nod1;
    int nod2;
};
vector<ceva>v;
vector<pair<int, int>>sol;
bool cmp( ceva a, ceva b){
    return a.cost<b.cost;
}
void union_(int nod1, int nod2){
    if(h[nod1]<h[nod2]){
        //il pun pe nod1 la nod2
        t[nod1]=nod2;
    }
    else{
        if(h[nod2]<h[nod1]){
            t[nod2]=nod1;
        }
        else{
            t[nod2]=nod1;
            h[nod1]++;
        }
    }
}
int find_(int nod){
    while(t[nod]!=nod){
        nod=t[nod];
    }
    return nod;
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>c;
        v.push_back({c, x, y});
    }
    sort(v.begin(), v.end(), cmp);
    for(int i=1;i<=n;i++){
        t[i]=i;
        h[i]=1;
    }
    for(int i=0;i<v.size();i++){
        int muchie=v[i].cost;
        int n1=v[i].nod1;
        int n2=v[i].nod2;
        int p1=find_(n1);
        int p2=find_(n2);
        if(p1!=p2){
            total+=muchie;
            union_(p1, p2);
            sol.push_back({n1, n2});
        }
    }
    cout<<total<<"\n";
    cout<<sol.size()<<"\n";
    for(int i=0;i<sol.size();i++)
        cout<<sol[i].first<<" "<<sol[i].second<<"\n";
}