#include <cstdio>
#include <cstring>
#define nmax 400000
using namespace std;
FILE *f1=fopen("apm.in","r"),*f2=fopen("apm.out","w");

int n,m,t[nmax],rg[nmax],cost,n1;
struct muchie
{
    int x,y,c;
}g[nmax],g1[nmax];

bool test(int x,int y)
{
    int i=x,j=y,aux;
    while(t[i]!=i)i=t[i];
    while(t[j]!=j)j=t[j];
    while(t[x]!=x){aux=t[x];t[x]=i;x=aux;}
    while(t[y]!=y){aux=t[y];t[y]=j;y=aux;}
    if(i==j)return true;
    else return false;
}

void join(int x,int y)
{
    int i=x,j=y;
    while(t[i]!=i)i=t[i];
    while(t[j]!=j)j=t[j];
    if(rg[x]>rg[y])t[j]=i;
    else t[i]=j;
    if(rg[x]==rg[y])rg[y]++;
}

int main()
{

    fscanf(f1,"%d%d",&n,&m);
    for(int i=0;i<m;i++)
    fscanf(f1,"%d%d%d",&g[i].x,&g[i].y,&g[i].c);

    for(int i=1;i<=n;i++)
            t[i]=i;
    memset(rg,1,nmax);

    for(int i=0;i<m-1;i++)
        for(int j=i+1;j<m;j++)
        if(g[i].c>g[j].c)
    {
        muchie aux;
        aux=g[i];
        g[i]=g[j];
        g[j]=aux;
    }

    for(int i=0;i<m;i++)
        if(test(g[i].x,g[i].y)==false)
        {
            cost+=g[i].c;
            join(g[i].x,g[i].y);
            n1++;
            g1[n1].x=g[i].x;
            g1[n1].y=g[i].y;
        }

    fprintf(f2,"%d\n%d\n",cost,n1);
    for(int i=1;i<=n1;i++)
        fprintf(f2,"%d %d\n",g1[i].x,g1[i].y);
    fclose(f1);
    fclose(f2);
    return 0;
}

//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.