#include <stdio.h>
#include <limits.h>
#include <fstream>
#include <iostream>

using namespace std;
int V;

int extrageMinim(int cheie[], bool boolQ[])
{
   int min = INT_MAX, minim;

   for (int v = 0; v < V; v++)
     if (boolQ[v] == false && cheie[v] < min)
         min = cheie[v], minim = v;

   return minim;
}

void apm(int *G[])
{
    int s=0;
     int p[V];
     int cheie[V];
     bool boolQ[V];
     for (int i = 0; i < V; i++)
        cheie[i] = INT_MAX, boolQ[i] = false;

     cheie[0] = 0;
     p[0] = -1;
     for (int i = 0; i < V-1; i++)
     {
        int u = extrageMinim(cheie, boolQ);
        boolQ[u] = true;

        for (int v = 0; v < V; v++)
          if (G[u][v] && boolQ[v] == false && G[u][v] <  cheie[v])
             {p[v]  = u; cheie[v] = G[u][v];s+=cheie[v];}
     }


    ofstream fout("apm.out");
	fout << s << endl << V-1 << endl;
	for (int i = 1; i < V; i++)
		fout << p[i] << " " << i << endl;
}

int main()
{
    ifstream fin("apm.in");
    int E,x,y,z,i,j;
   fin>>V>>E;
    int **G;
    G=new int*[V];
    for(i=0; i<V; i++)
        G[i] = new int[V];
    for(i=0;i<V;i++)
        for(j=0;j<V;j++)
            G[i][j]=0;
    for (int e = 0; e < E; e++)
	{
		fin >> x >> y >> z;
		G[x][y]=z;G[y][x]=z;
	}
	fin.close();

    apm(G);

    return 0;
}