#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;


struct muchie
{
    int x,y,c,*t=0,ok = 0;
    muchie(int X,int Y,int C)
    {
        x = X;
        y = Y;
        c = C;
    }
};

struct node
{
    int x;
    int val;
    node *urm=NULL;
}*q[200005];

bool comp(muchie a,muchie b)
{
    return a.c < b.c;
}

int N,M;
vector<muchie> v;

int sub[200005],K;
int *nod[200005],nr,cost;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1; i<=M; i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        v.push_back(muchie(x,y,c));
    }

    sort(v.begin(),v.end(),comp);


    for(vector<muchie>::iterator ii = v.begin(); ii!=v.end(); ii++)
    {
        int x = ii->x;
        int y = ii->y;
        int c = ii->c;

        if(nod[x]&&nod[y]&& *nod[x]==*nod[y])
            continue;
        cost +=c;
        nr++;
        ii->ok=1;

        if(nod[x]==0 && nod[y]==0) //subarbore nou
        {
            sub[++K] = K;
            q[K] = new node;
            q[K]->val = K;


            nod[x]=nod[y]=&sub[K];

        }
        else if(nod[x]==0 && nod[y]!=0) //adaugare la subarbore fara pos de ciclu
        {
            nod[x]=nod[y];

        }
        else if(nod[x]!=0 && nod [y]==0)//adaugare la subarbore fara pos de ciclu
        {
            nod[y]=nod[x];
        }
        else //contopire a 2 subarbori
        {
            int nou = min(*nod[y],*nod[x]);
            int vechi = max(*nod[y],*nod[x]);
            node *p;
            for(p= q[vechi]; p; p = p->urm )
            {
                sub[p->val]=nou;
            }
            p = q[nou];
            while(p->urm)
            {
                p = p->urm;
            }
            p->urm = q[vechi];
            q[vechi] = 0;
        }
    }
    printf("%d\n%d\n",cost,nr);
    for(vector<muchie>::iterator ii = v.begin(); ii!=v.end(); ii++)
    {
        if(ii->ok)
            printf("%d %d\n",ii->y,ii->x);
    }
    return 0;
}