#include <bits/stdc++.h>
#define eb emplace_back
#pragma GCC optimize("O3")
using namespace std;

typedef long long ll;

ifstream f("apm.in");
ofstream g("apm.out");

struct nod
{
    int x,y,c;
};

nod a;
ll n,m,cost,root[200005],arb[200005],ans;
vector<nod> v;
vector< pair<ll,ll> > sol;

bool cmp(const nod a,const nod b)
{
    return a.c<b.c;
}

ll getroot(ll x)
{
    if(root[x]==x) return x;
    return root[x]=getroot(root[x]);
}

void unite(int x,int y)
{
    ll rx=getroot(x);
    ll ry=getroot(y);
    if(rx!=ry)
    {
        if(arb[rx]<arb[ry]) swap(rx,ry);
        arb[rx]+=arb[ry];
        root[ry]=rx;
        ans+=cost;
        sol.eb(x,y);
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=n;i++) root[i]=i, arb[i]=1;
    for(int i=1;i<=m;i++)
    {
        f>>a.x>>a.y>>a.c;
        v.eb(a);
    }
    sort(v.begin(),v.end(),cmp);
    //for(auto e:v) cout<<e.x<<' '<<e.y<<' '<<e.c<<'\n';
    for(int i=0;i<m;i++)
    {
        cost=v[i].c;
        unite(v[i].x,v[i].y);
    }
    g<<ans<<'\n';
    g<<sol.size()<<'\n';
    for(auto e:sol) g<<e.first<<' '<<e.second<<'\n';
}