#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 400005
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
vector<int>Vct;
int n,m,ct=0;
int indice[nmax],x[nmax],y[nmax],c[nmax],gr[nmax];
int grupa(int i)
{
if(gr[i]==i) return i;

}
void reuniune(int i,int j)
{
gr[grupa(i)]=grupa(j);
}
bool compara(int i,int j)
{
return (c[i] < c[j]);
}
int main()
{
int i;
f>>n>>m;
for(i=1;i<=m;i++)
{
f>>x[i]>>y[i]>>c[i];
indice[i]=i;
}
for(i=1;i<=n;i++) gr[i]=i;
sort(indice+1,indice+m+1,compara);
for(i=1;i<=m;i++)
{
if(grupa(x[indice[i]])!=grupa(y[indice[i]]))
{
ct=ct+c[indice[i]];
reuniune(x[indice[i]],y[indice[i]]);
Vct.push_back(indice[i]);
}
}
g<<ct<<"\n";
g<<n-1<<"\n";
for(i=0;i<n-1;i++)
g<<x[Vct[i]]<<" "<<y[Vct[i]]<<"\n";
return 0;
}