#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");
int n, m, t[100001], rang[100001], cost, cnt;
struct muchii
{
int x, y, c;
}g[400001], arbore[400001];

int compara(muchii a, muchii b)
{
    return a.c<b.c;
}

int radacina(int nod)
{while(t[nod]!=nod)
nod=t[nod];

return nod;
}

void unificare(int a, int b)
{if(rang[a]<rang[b]) t[a]=b;
else if(rang[a]>rang[b]) t[b]=a;
else{
t[a]=b;
rang[b]++;
}
}

int main()
{int i, rx, ry;
fin>>n>>m;
for(i=1; i<=m; i++)
{fin>>g[i].x>>g[i].y>>g[i].c;
}

sort(g+1, g+m+1, compara);
//for(i=1; i<=m; i++)
   // cout<<g[i].x<<' '<<g[i].y<<' '<<g[i].c<<"\n";

for(i=1; i<=n; i++)
{t[i]=i;
rang[i]=1;
}

for(i=1; i<=m; i++)
{
rx=radacina(g[i].x);
ry=radacina(g[i].y);
if(rx!=ry)
{unificare(rx, ry);
cost+=g[i].c;
cnt++;
arbore[cnt].x=g[i].x;
arbore[cnt].y=g[i].y;
}

}
fout<<cost<<"\n"<<cnt<<"\n";
for(i=1; i<=cnt; i++)
    fout<<arbore[i].x<<' '<<arbore[i].y<<"\n";



    return 0;
}