#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#define pb push_back
#define NMax 200010
#define MMax 400010
#define nod pair<int, int>

using namespace std;

vector<nod> af;

struct muchie
{
    int x, y, c;
} mc[MMax];

bool compar (muchie a, muchie b)
{
    return a.c<b.c;
}
int N, M, multime[NMax], x, y, cost, i, l, suma;

int radacina (int x)
{
    int rad, y;

    rad=multime[x];
    while(multime[rad]!=rad)
    {
        rad=multime[rad];
    }

    while(multime[x]!=x)
    {
        y=multime[x];
        multime[y]=rad;
        x=y;
    }
    return rad;
}

void unire (int x, int y)
{
    multime[x]=y;
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&N,&M);

    for(i=1; i<=M; i++)
    {
        scanf("%d %d %d",&mc[i].x,&mc[i].y,&mc[i].c);
    }
    sort(mc+1, mc+M+1, compar);
    for(i=1; i<=N; i++)
        multime[i]=i;
    for(i=1; i<=M; i++)
    {
        x=mc[i].x;
        y=mc[i].y;
        cost=mc[i].c;
        if(radacina(x)!=radacina(y))
        {
            suma+=cost;
            unire(radacina(x), radacina(y));
            af.pb(nod(x,y));
        }
    }
    printf("%d\n",suma);
    l=af.size();
    printf("%d\n",l);
    for(i=0; i<l; i++)
        printf("%d %d\n",af[i].first, af[i].second);
    return 0;
}