#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
struct muchie{int x,y,c;};
vector<muchie> v(400000);
void sort(int l,int u)
{int i,m;
if(l>=u) return;
m=l;
for(i=l+1;i<=u;i++)
if(v[l].c>v[i].c)
{m++;
swap(v[i],v[m]);}
swap(v[l],v[m]);
sort(l,m-1);
sort(m+1,u);}
int main()
{ifstream f("apm.in");
ofstream h("apm.out");
int n,m,i,j,c[200000],d,k;
long long C=0;
vector<int> apm;
f>>n>>m;
for(i=1;i<=m;i++)	
f>>v[i].x>>v[i].y>>v[i].c;
sort(1,m);
j=1;
k=0;
for(i=1;i<=n;i++)
c[i]=i;
while(k<n-1)
{if(c[v[j].x]!=c[v[j].y])
{k++;
C=C+v[j].c;
apm.push_back(v[j].x);
apm.push_back(v[j].y);
d=c[v[j].y];
for(i=1;i<=n;i++)
if(c[i]==d)
c[i]=c[v[j].x];}
j++;}
h<<C<<"\n";
h<<k<<"\n";
for(i=0;i<apm.size();i++)
{h<<apm[i]<<" "<<apm[i+1]<<"\n";
++i;}	
return 0;}