#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");

int n,m,t[200010],rg[200010],i,q,x,y,c,tx,ty;

struct muchie{
int x,y;
long long c;
};

vector<muchie>v,v2;

int cautare(int nod)
{
    int r;
    r=nod;
    while(t[r]!=r)
        r=t[r];
    while(t[nod]!=nod)
    {
        nod=t[nod];
        t[nod]=r;
    }
    return r;
}

void unire(int x,int y)
{
    if(rg[x]>rg[y])
        t[y]=x;
    else
        t[x]=y;
    if(rg[x]==rg[y])
        rg[x]++;
}

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

int main()
{
    cin>>n>>m;
    for(i=1;i<=n;i++)
        t[i]=i,rg[i]=1;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        v.push_back({x,y,c});
    }
    sort(v.begin(),v.end(),cmp);
    c=0;
    for(i=0;i<m;i++)
    {
        tx=cautare(v[i].x);
        ty=cautare(v[i].y);
        if(tx!=ty)
        {
            v2.push_back({v[i].x,v[i].y,0});
            c+=v[i].c;
            unire(tx,ty);
        }
    }
    cout<<c<<'\n';
    cout<<v2.size()<<'\n';
    for(auto it:v2)
        cout<<it.x<<" "<<it.y<<'\n';
    return 0;
}