#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;

int n,m,qsv[400000],muchie[400000][3];
int cost,m1,muchii[400000][2];

struct comp_conex
{
    comp_conex* u;
}*nd,*nd1,*nod[200001];

stack <comp_conex*> q1,q2;

void qs(int st,int dr)
{
    int i=st,j=dr,mij=muchie[qsv[(i+j)/2]][2];
    while(i<=j)
    {
        while(muchie[qsv[i]][2]<mij&&i<dr) ++i;
        while(muchie[qsv[j]][2]>mij&&j>st) --j;
        if(i<=j)
        {
            swap(qsv[i],qsv[j]);
            ++i;--j;
        }
    }
    if(i<dr) qs(i,dr);
    if(j>st) qs(st,j);
}

int verifica(int x,int y)
{
    nd=nod[x];
    while(nd)
    {
        q1.push(nd);
        nd=nd->u;
    }
    nd1=nod[y];
    while(nd1)
    {
        q2.push(nd1);
        nd1=nd1->u;
    }
    nd=q1.top();
    q1.pop();
    nd1=q2.top();
    q2.pop();
    if(nd==nd1)
    {
        while(!q1.empty())
        {
            q1.top()->u=nd;
            q1.pop();
        }
        while(!q2.empty())
        {
            q2.top()->u=nd1;
            q2.pop();
        }
        return 1;
    }
    nd->u=nd1;
    while(!q1.empty())
    {
        q1.top()->u=nd1;
        q1.pop();
    }
    while(!q2.empty())
    {
        q2.top()->u=nd1;
        q2.pop();
    }
    return 0;
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    int i;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%d%d%d",&muchie[i][0],&muchie[i][1],&muchie[i][2]);
        qsv[i]=i;
    }
    for(i=1;i<=n;++i)
    {
        nod[i]=new comp_conex;
        nod[i]->u='\0';
    }
    qs(0,m-1);
    i=0;
    while(n>1&&i<m)
    {
        if(!verifica(muchie[qsv[i]][0],muchie[qsv[i]][1]))
        {
            cost+=muchie[qsv[i]][2];
            muchii[m1][0]=muchie[qsv[i]][0];
            muchii[m1++][1]=muchie[qsv[i]][1];
            --n;
        }
        ++i;
    }
    if(n>1) printf("WTF\n");
    else
    {
        printf("%d\n%d\n",cost,m1);
        for(i=0;i<m1;++i) printf("%d %d\n",muchii[i][0],muchii[i][1]);
    }
    return 0;
}