#include <fstream>
#include <algorithm>
#include <queue>
#define dim 400003
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m,cost_total,cnt;
int sz[dim],t[200003];
queue<pair<int,int> >Q;

struct muchie{
    int i,j,c;
}x[dim];

bool comp(muchie a,muchie b){
    return a.c<b.c;
}

int find(int val){
    if(t[val]!=val)
        t[val]=find(t[val]);
    
    return t[val];
}

void unio(int a,int b){
    int pa=find(a),pb=find(b);
    if(sz[pa]>sz[pb]){
        t[pb]=pa;
        sz[pa]++;
    }else{
        t[pa]=pb;
        sz[pb]++;
    }
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
        cin>>x[i].i>>x[i].j>>x[i].c;

    sort(x+1,x+m+1,comp);
    for(int i=1;i<=n;++i) t[i]=i,sz[i]=1;

    for(int i=1;i<=m;++i)
        if(find(x[i].i)!=find(x[i].j)){
            unio(x[i].i,x[i].j);
            cost_total+=x[i].c;
            Q.push({x[i].i,x[i].j});
            ++cnt;
        }
    cout<<cost_total<<'\n';
    cout<<cnt<<'\n';
    while(!Q.empty()){
        cout<<Q.front().first<<" "<<Q.front().second<<'\n';
        Q.pop();
    }

    return 0;
}