#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
const int inf = 1<<30;
const int maxn=2000;

int n,cost[maxn][maxn],parinte[maxn],d[maxn],viz[maxn];

void prim(int s)
{
    int i, j,nr=1;
    viz[s] = 1;

    for (i = 1; i <= n; i++){

        if (cost[s][i] != 0){
            parinte[i] = s;
            d[i] = cost[s][i];
        }
        else d[i] = inf;
    }
    parinte[s] = 0;
    d[s] = 0;

    int min,pmin;

    for (j = 1; j <= n - 1; j++){

        min = inf+1;
        for (i = 1; i <= n; i++)
            if (d[i] < min && viz[i] == 0){
                min = d[i];
                pmin = i;
            }
        viz[pmin] = 1;

        for (i = 1; i <= n; i++)
            if (d[i] > cost[pmin][i] && cost[pmin][i]!=0 && viz[i]==0 ){
                d[i] =  cost[pmin][i];
                parinte[i] = pmin;
            }

    }
}

int main()
{
    int i, j,k,m;
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    scanf( "%d %d", &n,&m);
    while ( m!=0){
           scanf("%d %d %d", &i, &j, &k);
        cost[i][j] = cost[j][i] = k;
        m--;
    }
   // srand(time(NULL));
    //int s = rand() % n;
    prim(1);
    int suma=0;
    for (i = 1; i <= n; i++)
        suma += d[i];
    printf("%d\n%d\n", suma, n - 1);
    for (i = 2; i <= n; i++)
        printf("%d %d\n", i, parinte[i]);

    return 0;
}