#include <cstdio>
#include <algorithm>
using namespace std;
struct NOD
{
    int x, y, c, ok;
};
NOD v[400005];
int t[200005],h[200005];
bool cmp(NOD a,NOD b)
{
    return a.c < b.c;
}
inline int findset(int x)
{
    while(t[x]!=x)
        x=t[x];
    return x;
}
inline void unionset(int x,int y)
{
    // x si y sunt radacini
    if (h[x] == h[y])
    {
        ++h[x];
        t[y] = x;
    }
    else if(h[x] < h[y])
        t[x] = y;
    else
        t[y] = x;
}
int main()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);
    int n, op, a, b, p, s, nr;
    scanf("%d%d", &n, &op);
    for (int i = 1; i <= n; ++i)
    {
        t[i] = i;
        h[i] = 1;
    }
    for (int i = 1; i <= op; ++i)
    {
          scanf("%d%d%d", &a, &b, &p);
          v[i].x = a;
          v[i].y = b;
          v[i].c = p;
    }
    sort(v + 1,v + op + 1, cmp);
    s = nr = 0;
    for (int i = 1; i <= op && nr < n;++i)
       if (findset(v[i].x) != findset(v[i].y))
       {
           unionset(findset(v[i].x),findset(v[i].y));
           v[i].ok = 1;
           s = s + v[i].c;
           ++nr;
       }
    printf("%d\n%d\n", s, n-1);
    for (int i = 1; i <= op; ++i)
        if (v[i].ok == 1)
            printf("%d %d\n",v[i].x,v[i].y);
    return 0;
}