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

using namespace std;

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

int n,m,i,t[200001],r[200001],nrm,nod1,nod2,s;
struct muchie
{
    int x,y,lung,marcat;
};
muchie a[400001];

bool compar(muchie x,muchie y)
{
    if(x.lung>=y.lung)
    {
        return 0;
    }
    return 1;
}

int radacina(int x)
{
    int r=x;
    while(t[r]!=r)
    {
        r=t[r];
    }
    while(t[x]!=x)
    {
        t[x]=r;
        x=t[x];
    }
    return r;
}

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

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>a[i].x>>a[i].y>>a[i].lung;
    }
    sort(a+1,a+m+1,compar);
    for(i=1;i<=n;i++)
    {
        t[i]=i;
        r[i]=1;
    }
    for(i=1;i<=m;i++)
    {
        nod1=a[i].x;
        nod2=a[i].y;
        if(radacina(nod1)!=radacina(nod2))
        {
            unire(radacina(nod1),radacina(nod2));
            a[i].marcat=1;
            nrm++;
        }
        if(nrm==n-1)
        {
            break;
        }
    }
    for(i=1;i<=m;i++)
    {
        if(a[i].marcat)
        {
            s=s+a[i].lung;
        }
    }
    g<<s<<'\n';
    g<<n-1<<'\n';
    for(i=1;i<=m;i++)
    {
        if(a[i].marcat)
        {
            g<<a[i].x<<" "<<a[i].y<<'\n';
        }
    }
    return 0;
}