#include <iostream>
#include <fstream>
#include <bitset>
#include <algorithm>
using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct ura
{
int x,y,c;
};
ura v[400001];
int t[200001], nr[200001];
int n,m;
bitset <400001> folosit;
bool cmp(ura a, ura b)
{
return (a.c<b.c);
}
int radacina(int x)
{
if(t[x]==0)
return x;
t[x]=radacina(t[x]);
return t[x];
}
bool verificare(int x, int y)
{
return (radacina(x)==radacina(y));
}
void reuniune(int x, int y)
{
int rx,ry;
rx=radacina(x);
ry=radacina(y);
if(nr[rx]<nr[ry]){
t[rx]=t[ry];
nr[ry]+=nr[rx];
}
else{
t[ry]=rx;
nr[rx]+=nr[ry];
}
}
int kruskal()
{
sort(v,v+m,cmp);
int i,cost,nrm;
i=0;
cost=0;
nrm=0;
while(nrm<n-1){
if(!verificare(v[i].x, v[i].y)){
folosit[i]=1;
nrm++;
cost+=v[i].c;
reuniune(v[i].x, v[i].y);
}
i++;
}
return cost;
}
int main()
{
in>>n>>m;
for(int i=0;i<m;i++)
in>>v[i].x>>v[i].y>>v[i].c;
out<<kruskal()<<'\n'<<n-1<<'\n';
for(int i=0;i<m;i++)
if(folosit[i])
out<<v[i].x<<' '<<v[i].y<<'\n';
return 0;
}