//#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
int sz[100005];
int tata[100005];
bool f[400005];
int sum;
pair<int,pair<int,int> > v[400005];
int big_daddy(int a){
    int aux=a;
    while(aux!=tata[aux]){
        aux=tata[aux];
    }
    while(a!=tata[a]){
        int auxi=tata[a];
        tata[a]=aux;
        a=auxi;
    }
    return aux;
}
bool check(int a,int b){
    if(big_daddy(a)==big_daddy(b))
        return true;
    return false;
}

void unite(int a,int b){
    int ta=big_daddy(a),tb=big_daddy(b);
    if(ta!=tb){
        if(sz[ta]>sz[tb]){
            tata[tb]=ta;
            sz[ta]+=sz[tb];
        }
        else{
            tata[ta]=tb;
            sz[tb]+=sz[ta];
        }
    }
}

void if_add(pair<int,pair<int,int> > a,int i){
    if(check(a.second.first,a.second.second)==false){
        unite(a.second.first,a.second.second);
        sum+=a.first;
        f[i]=1;
    }
}

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

int main()
{
    int n,m,cer,a,b,c;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        sz[i]=1;
        tata[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>a>>b>>c;
        v[i]=make_pair(c,make_pair(a,b));
    }
    sort(v+1,v+m+1);
    for(int i=1;i<=m;i++){
        if_add(v[i],i);
    }
    cout<<sum<<"\n"<<n-1<<"\n";
    for(int i=1;i<=m;i++){
        if(f[i]==1){
            cout<<v[i].second.first<<" "<<v[i].second.second<<"\n";
        }
    }
    return 0;
}