#include <iostream>

#include <stdio.h>

#define NN 101

#define infi 1000000000

using namespace std;

bool viz[NN];
int a[NN][NN],t[NN],n;
int vizitati[NN],loc;

void read()
{
    freopen("apm.in","r",stdin);

    int m;
int x,y,cost;
    scanf("%d%d", &n , &m);

    for(int i = 1; i <= m ; ++i)
    {
        scanf("%d%d%d", &x , &y , &cost);
        a[x][y]=cost;
        a[y][x]=cost;

    }

}

bool parcurg()
{
    for( int i=1 ; i <= n ; ++i)
        if(!viz[i])return true;
        return false;

}


int main()
{
    read();

    int cost=0,ce_adaug;

    int minim;
    vizitati[++loc]=1;
    viz[1]=true;
int nod_smecher;
    while(parcurg())
        //am n-1 pasi
    {
        minim=infi;

    for( int i = 1 ; i <= loc ; ++i)
        //ma uit in vectorul vizitatilor
    {


       int nod = vizitati[i];

       //in nod am la cine sunt now;
 for( int j = 1 ; j <=n ; ++j)
    if(a[nod][j]&&a[nod][j]<minim&&!viz[j]){
        minim=a[nod][j];
        nod_smecher=nod;
        ce_adaug=j;
    }

    }
cost+=minim;
    vizitati[++loc]=ce_adaug;
    viz[ce_adaug]=true;
    t[ce_adaug]=nod_smecher;
    }

    freopen("apm.out","w",stdout);
printf("%d\n",cost);
printf("%d\n",n-1);
for( int i = 1 ; i <=n ; ++i)
  if(t[i]!=0)
    printf("%d %d\n",i,t[i]);

    return 0;
}