//prim
#include <stdio.h>
#define Nmax 200001
#define Mmax 400001
struct graf { int nod, cost; graf * next; } *g[Nmax];
int N, M, i, x, y, z, min = 0x3f3f3f3f, poz,s;
struct muchie { int x, y, c; } h[Mmax],rez[Nmax];
int nrH, nr;
char uz[Nmax];
inline void swap(muchie &a, muchie &b) { muchie tmp = a; a = b; b = tmp; }
void upHeap(int loc)
{
if (loc == 1) return;
int tata = loc << 1;
if (h[tata].c > h[loc].c) swap(h[tata],h[loc]), upHeap(tata);
}
void downHeap(int loc)
{
int fiu = loc << 1;
if (fiu > nrH) return;
if (fiu+1 <= nrH && h[fiu+1].c < h[fiu].c) ++fiu;
if (h[loc].c > h[fiu].c) swap(h[loc],h[fiu]), downHeap(fiu);
}
void pushHeap(int a, int b, int cost)
{
muchie tmp; tmp.x = a; tmp.y = b; tmp.c =cost;
h[++nrH] = tmp;
upHeap(nrH);
}
void popHeap()
{
swap(h[1],h[nrH--]);
downHeap(1);
}
int main()
{
for (freopen("apm.in", "r", stdin), scanf("%d %d\n", &N, &M), i = 1; i<=M; ++i)
{
scanf("%d %d %d\n", &x, &y, &z);
if (z < min) min = z, poz = x;
graf * q = new graf; q->nod = y; q->cost = z; q->next = g[x]; g[x] = q;
q = new graf; q->nod = x; q->cost = z; q->next = g[y]; g[y] = q;
}
uz[poz] = 1;
for (graf * p = g[poz]; p; p = p->next) pushHeap(poz,p->nod,p->cost);
while (nrH && nr < N-1)
{
while (uz[h[1].x] && uz[h[1].y]) popHeap();
rez[++nr] = h[1];
poz = h[1].x;
if (uz[poz]) poz = h[1].y;
uz[poz] = 1;
s+=h[1].c;
popHeap();
for (graf *p = g[poz]; p; p = p->next) pushHeap(poz,p->nod,p->cost );
}
for (freopen("apm.out", "w", stdout), printf("%d\n%d\n", s, N-1), i = 1; i<=nr; ++i) printf("%d %d\n", rez[i].x, rez[i].y);
return 0;
}