#include <iostream>
#include <cstdio>
#include <algorithm>
#define Mmax 400005
#define Nmax 200005

using namespace std;

struct  muchie
{
    int x,y,c;
}a[Mmax],p[Nmax];

int n,m,cost;
int t[Nmax];

void citire()
{
    scanf("%d%d",&n,&m);
    for (int i=1; i<=m; i++)
        scanf("%d%d%d",&a[i].x, &a[i].y, &a[i].c);
}

void initializare_sir_tati()
{
    for (int i=1; i<=n; i++)
        t[i]=i;
}

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

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

void reuniune(int x, int y)
{
    t[radacina(y)]=radacina(x);
}

void formare_apm()
{
    int contor_muchii=0;
    initializare_sir_tati();
    for (int i=1; i<=m && contor_muchii<n-1; i++)
    {
        if (radacina(a[i].x) != radacina(a[i].y))
        {
            reuniune(a[i].x, a[i].y);
            cost+=a[i].c;
            contor_muchii++;
            p[contor_muchii]=a[i];
        }
    }
}

void afisare()
{
    printf("%d\n%d\n",cost,n-1);
    for (int i=1; i<=n-1; i++)
        printf("%d %d\n",p[i].x, p[i].y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    sort(a+1, a+m+1, cmp);
    formare_apm();
    afisare();

    return 0;
}