#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount




ifstream fin("apm.in"); ofstream fout("apm.out");
#define cin fin
#define cout fout


int n, m;
pair<int, pii> edge[400010];





//disjoint set union

int rep[200010], sz[200010];

void initialize(){
    for(int i=1; i<=n; i++){
        rep[i]=i;
        sz[i]=1;
    }
}


int get_rep(int u){

if(u!=rep[u]){
    rep[u]=get_rep(rep[u]);
    return rep[u];
}
else{
    return u;
}

}


void unite(int u, int v){

if(sz[u]>sz[v]){
    sz[u]+=sz[v];
    rep[v]=u;
}
else{
    sz[v]+=sz[u];
    rep[u]=v;
}

}


int32_t main(){
INIT
cin>>n>>m;
for(int i=1; i<=m; i++){
    cin>>edge[i].sc.ft>>edge[i].sc.sc>>edge[i].ft;
}

initialize();

vector<pii> edges;
int sum=0;

sort(edge+1, edge+1+m);
for(int i=1; i<=m; i++){
    //muchia uneste doua multimi disjuncte, sau nu
    int u, v, c;
    u=edge[i].sc.ft, v=edge[i].sc.sc, c=edge[i].ft;

    int ru=get_rep(u), rv=get_rep(v);
    if( ru==rv ){
        continue;
    }
    else{
        unite(ru, rv);
        sum+=c;
        edges.pb({u, v});
    }
}

cout<<sum<<"\n";
cout<<edges.size()<<"\n";
for(auto pr:edges){
    cout<<pr.ft<<" "<<pr.sc<<"\n";
}

return 0;
}