#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");
struct graf{int i,j,c,ok;}v[400001];
int ct;
int a[400001];
int n,m;
void citire(){
f>>n>>m;
for(int z=1;z<=m;z++)
        f>>v[z].i>>v[z].j>>v[z].c;

for(int i=1;i<=n;i++)
a[i]=i;
}
void sortare(){
int ok,nr=0;
do{ ok=1;
    for(int i=1;i<m;i++)
    if(v[i].c>v[i+1].c){
        graf aux=v[i];
        v[i]=v[i+1];
        v[i+1]=aux;
        ok=0;

    }
}while(!ok);
}
void apm(){
for(int i=1;i<=m;i++)
if(a[v[i].i]!=a[v[i].j]){
    v[i].ok=1;
    ct+=v[i].c;
    int mini=min(a[v[i].i],a[v[i].j]);
    int maxi=max(a[v[i].i],a[v[i].j]);
    a[v[i].i]=a[v[i].j]=mini;
for(int j=1;j<=n;j++)
    if(a[j]==maxi) a[j]=mini;
}
}
void afis(){
g<<ct<<endl<<n-1<<endl;
for(int i=1;i<=m;i++)
    if(v[i].ok==1) g<<v[i].i<<" "<<v[i].j<<endl;
}
int main()
{
    citire(); sortare(); apm(); afis();
    return 0;
}