#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
struct muchie{int x,y,c;};
vector<muchie> v(400000);
class Compara
{public:
bool operator()(const muchie& x, const muchie& y) const
{return x.c < y.c;}};
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=0;i<m;i++)	
f>>v[i].x>>v[i].y>>v[i].c;
make_heap(v.begin(),v.begin()+m,Compara());	
sort_heap(v.begin(),v.begin()+m,Compara());	
j=0;
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;}