#include<iostream>
#include<set>
#include<vector>
using namespace std;

#define NMAX 200002

int n,m,root[NMAX];
set<pair<int,pair<int,int>>>dsu;
int get_root(int x){
    if(x==root[x])return x;
    return root[x]=get_root(root[x]);
}
void join(int x,int y){
    x=get_root(x);
    y=get_root(y);
    root[y]=x;
}
bool joined(int x,int y){
    return get_root(x)==get_root(y);
}
signed main(){
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif // LOCAL
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;++i)root[i]=i;
    for(int i=1;i<=m;++i){
        int x,y,z;
        cin>>x>>y>>z;
        dsu.insert(make_pair(z,make_pair(x,y)));
    }
    long long sum=0x0;
    vector<pair<int,int>>sol;
    while(dsu.size()){
        auto it=dsu.begin();
        int x=it->second.first,y=it->second.second,c=it->first;
        dsu.erase(it);
        if(!joined(x,y)){
            join(x,y);
            sol.push_back(make_pair(x,y));
            sum+=c;
        }
    }
    cout<<sum<<"\n"<<sol.size()<<"\n";
    for(auto it=sol.begin();it!=sol.end();++it){
        cout<<it->first<<" "<<it->second<<"\n";
    }
    return 0;
}