#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMax 200005
#define MMax 400005
using namespace std;
struct Muchie
{
int x,y,z;
}Edge[MMax];
int N,M,x,y,z,tata[NMax],rang[NMax],cost,rad;
vector<pair<int,int> > Sol;
inline bool comp(Muchie a,Muchie b)
{
return a.z<b.z;
}
void Read()
{
scanf("%d%d",&N,&M);
for(int i=1;i<=M;i++)
{
scanf("%d%d%d",&Edge[i].x,&Edge[i].y,&Edge[i].z);
}
}
int Radacina(int x)
{
for(rad=x;rad!=tata[rad];rad=tata[rad]);
return rad;
}
void Sudeaza(int x,int y)
{
if(rang[x]>rang[y])
tata[y]=x;
else tata[y]=x;
if(rang[x]==rang[y])
rang[y]++;
}
void Solve()
{
for(int i=1;i<=N;i++)
{
tata[i]=i;
rang[i]=1;
}
sort(Edge+1,Edge+M+1,comp);
for(int i=1;i<=M;i++)
{
int x=Edge[i].x;
int y=Edge[i].y;
int radx=Radacina(x);
int rady=Radacina(y);
if(radx!=rady)
{
Sudeaza(radx,rady);
cost=cost+Edge[i].z;
Sol.push_back(make_pair(Edge[i].x,Edge[i].y));
}
}
}
void Write()
{
printf("%d\n%d\n",cost,Sol.size());
for(vector<pair<int,int> >::iterator it=Sol.begin();it!=Sol.end();it++)
printf("%d %d\n",it->first,it->second);
}
int main()
{
freopen("apm.in","r",stdin);
freopen("apm.out","w",stdout);
Read();
Solve();
Write();
}