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

using namespace std;

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

const int N=200001;
int  h[N],t[N],n,m;

struct cost
{
    int x,y,c;

} v[2*N],muchie[2*N];

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

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

void unioni (int x, int y)
{
    int rx=radacina(x),ry=radacina(y);

    if (h[rx]<h[ry])
    {
        t[rx]=ry;
    }
    else
    {
        t[ry]=rx;

        if (h[rx]==h[ry])
        {
            ++h[ry];
        }
    }
}


int main()
{
    int s=0,i,nr=0;

    f>>n>>m;
    for (i=1; i<=m; i++)
    {
        f>>v[i].x>>v[i].y>>v[i].c;
    }

    sort (v+1,v+m+1,cmp);

    i=1;
    while (nr < n - 1)
    {
        if ( radacina( v[i].x ) != radacina( v[i].y ) )
        {
            unioni(v[i].x,v[i].y);

            muchie[++nr].x = v[i].x;
            muchie[nr].y = v[i].y;

            s+=v[i].c;
        }
        i++;
    }

    g<<s<<'\n'<<n-1<<'\n';

    for (i=1;i < n;i++)
        g<<muchie[i].y<<" "<<muchie[i].x<<'\n';

    return 0;
}