#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define FIN "apm.in"
#define FOUT "apm.out"
#define MAX_N 200005
#define MAX_E 400005

int N, M;

typedef struct edge
{
        int n1, n2;
        int c;
        unsigned char l;
};

edge E[MAX_E];

int T[MAX_N]; // disjoint set
int H[MAX_N];

struct cmp
{
     bool operator () (const edge &a, const edge &b) const
     {
          if (a.c < b.c) return 1;
          return 0;
     }  
};

    int tata (int c)
    {
        while (T[c] != c)
            c = T[c];
    }

    int main ()
    {
        int i, nluat = 0, cost = 0;
        
        freopen (FIN, "r", stdin);
        freopen (FOUT, "w", stdout);
        
        scanf ("%d %d", &N, &M);
        for (i = 1; i <= M; ++i)
            scanf ("%d %d %d", &E[i].n1, &E[i].n2, &E[i].c);
        
        sort (E + 1, E + M + 1, cmp());
        for (i = 1; i <= N; ++i) T[i] = i, H[i] = 1;
        
        for (i = 1; nluat < N - 1; ++i)
        {
            int t1 = tata (E[i].n1);
            int t2 = tata (E[i].n2);
            
            if (t1 != t2)
            {
                   ++nluat, cost += E[i].c;
                   E[i].l = 1;
                   if (H[t1] > H[t2]) T[t2] = t1;
                   if (H[t1] < H[t2]) T[t1] = t2;
                   
                   if (H[t1] == H[t2])
                      T[t1] = t2, ++H[t2];
            }
        }
        
        printf ("%d\n%d\n", cost, N - 1);
        for (i = 1; i <= M; ++i)
            if (E[i].l == 1) printf ("%d %d\n", E[i].n1, E[i].n2, E[i].c);
        
        return 0;
    }