#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

vector<pair<int,int>> rasp1;
struct con{
    int nod1,nod2,val;
}v[400001];
int tata[200001];

bool cmp(con a,con b){
    return a.val<b.val;
}

int ftata(int a){
    if(tata[a]!=a){
        tata[a]=ftata(tata[a]);
    }
    return tata[a];
}

int main()
{
    int n,m,i,tata1,tata2,rasp=0;
    cin>>n>>m;
    for(i=1;i<=n;i++){
        tata[i]=i;
    }
    for(i=0;i<m;i++){
        cin>>v[i].nod1>>v[i].nod2>>v[i].val;
    }
    sort(v,v+m,cmp);
    for(i=0;i<m;i++){
        tata1=ftata(v[i].nod1);
        tata2=ftata(v[i].nod2);
        if(tata1!=tata2){
            rasp+=v[i].val;
            tata[tata1]=tata2;
            rasp1.push_back({v[i].nod1,v[i].nod2});
        }
    }
    cout<<rasp<<"\n"<<rasp1.size()<<"\n";
    for(i=0;i<rasp1.size();i++){
        cout<<rasp1[i].first<<" "<<rasp1[i].second<<"\n";
    }
    return 0;
}