#include<fstream>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
 
void Citire();
void QS(int st,int dr);
void Kruskal();
int find(int x);
int Union(int rad1, int rad2);
//void unific(int x,int y);
void Afisare();
int m,n,cost;
//int conex[100];
int tata[200009],h[200009];
int contor;
 
struct muchie
{
int x;
int y;
int c;
};
muchie v[400009],x;
 
int main()
{
Citire();
QS(1,m);
Kruskal();
Afisare();
}
void Citire()
{
int i;
int xx,yy,cc;
fin>>n>>m;
for(i=1;i<=m;i++)
{
fin>>xx>>yy>>cc;
v[i].x=xx;
v[i].y=yy;
v[i].c=cc;
}
for(i=1;i<=n;i++)
//conex[i]=i;
tata[i]=-1;//fiecare componenta conexa este independenta
}

void QS(int st,int dr)
{
if(st<dr)
{
int i,j;
i=st;j=dr;
muchie z;
z=v[st];
while(i<j)
{
while(i<j &&v[j].c>=z.c) j--;
v[i]=v[j];
while(i<j &&v[i].c<=z.c) i++;
v[j]=v[i];
}
v[i]=z;
QS(st,i-1);
QS(i+1,dr);
}
}
void Kruskal()
{
int rad1,rad2;
int i;
while(contor<n-1)
{
for(i=1;i<=m;i++)
/*if(conex[v[i].x]!=conex[v[i].y])//nu apartin aceleasi componente conexe
{cost+=v[i].c;v[i].c=-1;unific(conex[v[i].x],conex[v[i].y]);}*/
{

rad1=find(v[i].x);
rad2=find(v[i].y);
if(rad1!=rad2)
{
cost+=v[i].c;
v[i].c=-1;
contor++;
Union(rad1,rad2);
}
}
}
}
/*void unific(int x,int y)//il inlocuiesc peste tot pe x cu y
{
int i;
for(i=1;i<=n;i++)
if(conex[i]==x)
conex[i]=y;
}*/
void Afisare()
{
int i;
fout<<cost<<'\n';
fout<<contor<<'\n';
for(i=1;i<=m;i++)
if(v[i].c==-1)
fout<<v[i].x<<' '<<v[i].y<<'\n';
}
 
int find(int x)

{

int rad,y;

rad=x;

while(tata[rad]!=-1) rad=tata[rad];

/*while(tata[x]!=rad)
{
y=tata[x];
tata[x]=rad;
x=y;
}*/

return rad;

}

int Union(int rad1,int rad2)

{
if(h[rad1]<h[rad2])
tata[rad1]=rad2;
else
{
tata[rad2]=rad1;
if(h[rad1]==h[rad2])
h[rad1]++;
}
}
//nu mai avem nevoie de vectorul CONEX.