#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct {int x,y,c;}MUCHIE;
MUCHIE v[400010],u[400010];
int n,m,T[200010],R[200010],cost,k;

bool verif(MUCHIE a,MUCHIE b) { return (a.c < b.c ); }

void citire()
{
    FILE*f=fopen("apm.in","r");
    fscanf(f,"%d%d",&n,&m);
    for(int i=0;i<m;i++)
        fscanf(f,"%d%d%d",&v[i].x,&v[i].y,&v[i].c);
    fclose(f);
}

int find(int x)
{
    if(T[x] == x) return x;
    T[x] = find(T[x]);

    return T[x];
}

void merge(int x,int y)
{
    if(R[x] == R[y])
    {
        ++R[x];
        T[y] = x;
    }
    else
        if(R[x] > R[y])
            T[y] = x;
        else T[x] = y;
}

void kruskal()
{
    for(int i=1;i<=n;++i)
       {  T[i] = i ; R[i] = 0; }
    sort(v,v+m,verif);
    for(int i=0;i<m && k < n; ++i)
    {
        if( find(v[i].x) != find(v[i].y) )
        {
            u[++k] = v[i];
            cost += v[i].c;

            merge(find(v[i].x), find(v[i].y));
        }
    }
}

void scrie()
{
    FILE *f=fopen("apm.out","w");
    fprintf(f,"%d\n%d\n",cost,n-1);
    for(int i=1;i<n;++i)
        fprintf(f,"%d %d\n",u[i].x,u[i].y);
    fclose(f);
}

int main()
{
    citire();
    kruskal();
    scrie();
    return 0;
}