#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
ll t,n,m,i,j,a,b,c,d,h,parent[200006],sz[200006],mini;
vector<tuple<int,int,int>>e;
vector<pair<int,int>>ans;
void make_set(ll node){
    parent[node]=node;
    sz[node]=1;
}
ll par(ll node){
    if (parent[node]==node){
        return node;
    }
    return parent[node]=par(parent[node]);
}
bool union_set(ll a,ll b){
    ll x=par(a);
    ll y=par(b);
    if (x!=y){
        if (sz[x]<sz[y])swap(x,y);
        parent[y]=x;
        sz[x]+=sz[y];
        mini+=c;
        ans.push_back({a,b});
    }
}
int main()
{   f>>n>>m;
    for (i=1;i<=n;i++)make_set(i);
    for (i=1;i<=m;i++){
        f>>a>>b>>c;
        e.push_back({c,a,b});
    }
    sort (e.begin(),e.end());
    for (i=0;i<m;i++){
        tie(c,a,b)=e[i];
        union_set(a,b);

    }
    g<<mini<<'\n';
    g<<ans.size()<<'\n';
    for (i=0;i<ans.size();i++){
        g<<ans[i].first<< ' ' <<ans[i].second<<'\n';
    }
    return 0;
}