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

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

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

void join(int x,int y)
{
    int i=x;
    while(t[i]!=i)i=t[i];
    t[i]=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;

    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.