#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

struct apm{
int x,y,cost;
}muchie[400005],retin[400005];

bool cmp(apm a,apm b)
{
    return a.cost<b.cost;
}

int t[200005],i,n,m,x1,y1,s,cnt;

int radacina(int x)
{
    if(t[x]==0)
        return x;
    else
    {
        int k=radacina(t[x]);
        t[x]=k;
        return k;
    }
}

void unire(int a,int b)
{
    int rx=radacina(a),ry=radacina(b);
    if(rx!=ry)
    {
        t[rx]=ry;
    }
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>muchie[i].x>>muchie[i].y>>muchie[i].cost;
    }
    for(i=1;i<=n;i++)
    t[i]=0;
    sort(muchie+1,muchie+m+1,cmp);
    for(i=1;i<=m;i++)
    {
        if(radacina(muchie[i].x)!=radacina(muchie[i].y))
        {
            s=s+muchie[i].cost;
            unire(muchie[i].x,muchie[i].y);
            cnt++;
            retin[cnt].x=muchie[i].x,
            retin[cnt].y=muchie[i].y;
        }
    }
    g<<s<<'\n';
    g<<cnt<<'\n';
    for(i=1;i<=cnt;i++)
        g<<retin[i].x<<" "<<retin[i].y<<'\n';
    return 0;
}