#include <iostream>
#include <fstream>
#include <vector>
#include <cassert>

#define INFINIT 1000000000
#define NMAX 200005
using namespace std;

ifstream fin("apm.in");
ofstream fout("apm.out");

int n ,         //numarul de noduri
        v[NMAX], //vector de vizitati cu în care marchez nodurile adăugate în APM
        d[NMAX], // d[k] = distanța minimă de la un nod din arbore la nodul incă neadăugat k
        t[NMAX], //vectorul de tați pentru arbore
        H[NMAX], nH, //un heap cu nodurile și dimenaiune asa. Criteriul de ordonare pentru heap este d[]
        vpoz[NMAX] //vectorul cu pozitia fiecarui nod in heap;
        ;

vector<pair<int,int> > G[NMAX];

void stergeDinHeap(int indice)
{
    //sterg din heap elementul de indice precizat
    H[indice] = H[nH--];
    vpoz[H[indice]] = indice;
    int esteHeap = 0, i = indice, k, aux;
    while(!esteHeap  && 2 * i <= nH){
        k = 2 * i;
        if(k + 1 <= nH && d[H[k]] > d[H[k+1]])
            k++;
        if(d[H[k]] > d[H[i]])
            esteHeap = 1;
        else{
            aux = H[i]; H[i] = H[k]; H[k] = aux;
            vpoz[H[i]] = i;
            vpoz[H[k]] = k;
            i = k;
        }
    }
}
 
void muta_sus(int indice)
{
    //muta in heap in sus elementul de indice dat
    int esteHeap = 0, i = indice , aux;
    while(!esteHeap && i / 2 > 0)
        if(d[H[i]] >= d[H[i/2]])
            esteHeap = 1;
        else{
            aux = H[i]; H[i] = H[i / 2]; H[i / 2] = aux;
            vpoz[H[i]] = i;
            vpoz[H[i / 2]] = i / 2;
            i /= 2;
        }
}

int main()
{
    int i , j , c , m;
    fin >> n >> m;
    
    while( m )
    {
		fin >> i >> j >> c;
        assert(c > 0);
    	G[i].push_back(make_pair(j , c));
        G[j].push_back(make_pair(i , c));
    	m --;
	}
	nH = n;
	for(i = 1 ; i <= n ; i ++ )
	{
		v[i] = 0;
		d[i] = INFINIT;
		H[i] = i;
        vpoz[i] = i;
	}
	v[1] = 1; // vectorul de vizitati
	t[1] = 0; //vectorul de tati
	d[1] = 0; // vectorul cu costurile 
	stergeDinHeap(1);
    for(auto x : G[1]){
        d[x.first] = x.second;
        t[x.first] = 1;
        muta_sus(x.first);
    }
	for(int k = 1 ; k < n ; ++k)
	{
		int nod = H[1];
        stergeDinHeap(1);
		if(d[nod] < INFINIT)
		{
			v[nod] = 1;
			// verificam daca varful adaugat in arbore nu imbunatateste costurile de legare la arbore a varfurilor inca nevizitate
            for(auto x : G[nod])
                if(!v[x.first] && d[x.first] > x.second)
                {
                    d[x.first] = x.second;
                    t[x.first] = nod;
                    muta_sus(vpoz[x.first]);
                }
		}
	}
	int S = 0;
	for(i = 1 ; i <= n ; ++i)
		S += d[i];	
	fout << S << "\n" << n - 1 << "\n";
	for(i = 1 ; i <= n ; ++i)
        if(t[i])
            fout << t[i] << " " << i << "\n";
	
    return 0;
}