#include <stdio.h>

#define Nmax 200200
#define Mmax 400400

struct muchie { int a,b,c; char ok;};

muchie l[Mmax];
int t[Nmax], r[Nmax], n,m,sum;

int mul(int x)
{
    if (t[x] == x) return t[x];
    t[x] = mul(t[x]);
    return t[x];    
}

int combina(int x,int y)
{
    x = mul(x);
    y = mul(y);
    if (r[x] > r[y])
    {
        t[y] = x;    
    }    
    else
    {
        t[x] = y;
        if (r[x] == r[y]) ++r[y];    
    }
}

int cmp(muchie a,muchie b)
{
    if (a.c < b.c) return 1;
    if (a.c > b.c) return -1;
    return 0;        
}

void sort(int st,int dr)
{
    int i=st,j=dr;
    muchie sch=l[(i+j)/2],tmp;
    do{
        while (cmp(l[i],sch)==1) ++i;
        while (cmp(sch,l[j])==1) --j;
        if (i<=j)
        {
            tmp = l[i];
            l[i] = l[j];
            l[j] = tmp;
            ++i; --j;    
        }
    } while (i<=j);
    if (i<dr) sort(i,dr);
    if (st<j) sort(st,j);       
}

void init()
{
    for (int i=1;i<=n;++i)
    t[i] = i;    
}

void afis()
{
    freopen("apm.out","w",stdout);    
    printf("%d\n", sum);
    printf("%d\n", n-1);
    for (int i=1;i<=m;++i)  if (l[i].ok)
    printf("%d %d\n", l[i].a, l[i].b);      
}

void kruskal()
{
    sort(1,m);
    for (int i=1;i<=m;++i)
    {
        int m1,m2;
        m1 = mul(l[i].a);
        m2 = mul(l[i].b);
        if (m1!=m2)
        {
            sum += l[i].c;
            l[i].ok = 1;
            combina(m1,m2);    
        }    
    }    
}

void cit()
{
    freopen("apm.in","r",stdin);
    scanf("%d%d", &n, &m);
    for (int i=1;i<=m;++i)
    scanf("%d%d%d", &l[i].a, &l[i].b, &l[i].c);
}

void solve()
{
    cit();
    init();
    kruskal();
    afis();    
}

int main()
{
    solve();    
    
    return 0;    
}