#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;
struct muchie {
    ll cost;
    ll u;
    ll v;
}e[400007];
vector<muchie>ans;
int cmp(muchie a, muchie b){
    if (a.cost<=b.cost)return 1;
    return 0;
}
void make_set(ll node){
    parent[node]=node;
    sz[node]=1;
}
int par(ll node){
    if (parent[node]==node){
        return node;
    }
        //cout<<node<<' ';


    sz[node]=2e9;
    return parent[node]=par(parent[node]);
}
void union_set(int a,int b){
    int x=par(a);
    int 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(e[i]);
    }
}
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[i]={c,a,b};
    }
    sort (e+1,e+m+1,cmp);
    for (i=1;i<=m;i++){
        a=e[i].u;
        b=e[i].v;
        c=e[i].cost;
        //cout<<c<<'\n';
        union_set(a,b);

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