#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
struct muchie{int x,y,c;};
vector<muchie> v(400000);
void sort(int l,int r)
{int i, j;
muchie y,x;
i=l; j=r; x=v[(l+r)>>1];
while (i<=j)
{ while (v[i].c<x.c) 
++i;
while (x.c<v[j].c)
j--;if (i<=j)
{swap(v[i],v[j]);
++i;--j;}}
if (l<j) sort(l,j);
if (i<r) sort(i,r);}
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;}