#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define nmax 200005
#define mmax 400005
using namespace std;
FILE *fin, *fout;
int n,m,t[nmax],r[nmax],nm[2][nmax],rez=0,nr=0;
struct muchie
{
    int x,y,c;
}v[mmax];
void quicksort(int x, int y)
{
    muchie pivot=v[(x+y)/2],temp;
    int i=x,j=y;
    while(i<=j)
        {
            while(v[i].c<pivot.c)
                i++;
            while(v[j].c>pivot.c)
                j--;
            if(i<=j)
            {
                temp=v[i];
                v[i]=v[j];
                v[j]=temp;
                i++;
                j--;
            }
        }
    if(x<j)
        quicksort(x,j);
    if(i<y)
        quicksort(i,y);
}
void unite(int x,int y)
{
   if(r[x]>=r[y])
        t[y]=x;
   else
        t[x]=y;
   r[y]+=(r[y]==r[x]);
}
int cauta(int x)
{
    int tata,temp;
    for(tata=x;tata!=t[tata];tata=t[tata]);
    return tata;
}
int main()
{
    fin=fopen("apm.in","r");
    fout=fopen("apm.out","w");
    fscanf(fin,"%d %d",&n,&m);
    int t1,t2;
    for(int i=1;i<=m;i++)
        fscanf(fin,"%d %d %d",&v[i].x,&v[i].y,&v[i].c);
    quicksort(1,m);
    for(int i=1;i<=n;i++)
        t[i]=i,r[i]=1;
    for(int i=1;i<=m && nr<n-1;i++)
    {
        t1=cauta(v[i].x);
        t2=cauta(v[i].y);
        if(t1!=t2)
            unite(t1,t2),rez+=v[i].c,nm[0][++nr]=v[i].x,nm[1][nr]=v[i].y;
    }
    fprintf(fout,"%d\n%d\n",rez,nr);
    for(int i=1;i<=nr;i++)
        fprintf(fout,"%d %d\n",v[i].x,v[i].y);
    return 0;
}