#include<stdio.h>
#include<algorithm>

using namespace std;

#define Nmax 200010
#define Mmax 400010

struct muchi
{
    int x,y,c,ok;
} v[Mmax];

int N,M,arb[Nmax];

bool cmp(muchi i,muchi j)
{
    return (i.c<j.c);
}

void unite(int x,int y)
{
    int a=x,b;
    for(; arb[x] ; x=arb[x]);
    while( arb[a] )
        {
        b=arb[a];
        arb[a]=y;
        a=b;
        }

    arb[x]=y;
}

int find(int x)
{
    for(; arb[x] ; x=arb[x]);
    return x;
}

void solve()
{
    sort(v+1,v+M+1,cmp);

    int Sum=0;
    for(int i=1;i<=M;++i)
        if (find(v[i].x)!=find(v[i].y))
            {
            v[i].ok=1;
            Sum += v[i].c;
            unite(v[i].x,v[i].y);
            }

    printf("%d\n%d\n",Sum,N-1);
    for(int i=1;i<=M;++i)
        if (v[i].ok)
            printf("%d %d\n",v[i].x,v[i].y);
}

void cit();

int main()
{
    cit();
    solve();
    return 0;
}

void cit()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)
        scanf("%d%d%d",&v[i].x,&v[i].y,&v[i].c);
}