#include <bits/stdc++.h>

using namespace std;
struct muchie
{
    int x,y,c;
};
muchie v[400005];
int t[200005],h[200005];
bool ve[400005];
bool cmp(muchie a,muchie b)
{
    return a.c < b.c;
}
int gasire(int x)
{
    while(x != t[x])
        x = t[x];
    return x;
}
bool combinare(int x,int y)
{
    int tx,ty;
    tx = gasire(x);
    ty = gasire(y);
    if(tx == ty)
        return 0;
    else if (h[tx] == h[ty])
    {
        h[tx]++;
        t[ty] = tx;
    }
    else if(h[tx] < h[ty])
        t[tx] = ty;
    else
        t[ty] = tx;
    return 1;
}
int main()
{
    freopen("apm.in", "r",stdin);
    freopen("apm.out", "w",stdout);
    int n,m,cost = 0,i;
    bool vrs;
    scanf("%d%d", &n, &m);
    for(i = 1;i <= m;i++)
        scanf("%d%d%d", &v[i].x, &v[i].y, &v[i].c);
    sort(v + 1,v + m + 1,cmp);
    for(i = 1;i <= n;i++)
    {
        t[i] = i;
        h[i] = 1;
    }
    for(i = 1;i <= m;i++)
    {
        if(combinare(v[i].x,v[i].y) == 1)
        {
            cost += v[i].c;
            ve[i] = 1;
        }
    }
    printf("%d\n%d\n",cost,n - 1);
    for(i = 1;i <= m;i++)
    {
        if(ve[i] == 1)
            printf("%d %d\n",v[i].y,v[i].x);
    }
    return 0;
}