# include <cstdio>
# include <algorithm>

using namespace std;

# define FIN "apm.in"
# define FOUT "apm.out"
# define MAXN 200005
# define MAXM 400005

struct muchie
{
   int x, y, c;
} H[MAXM];

int N, M, i, cost, ct;
int T[MAXN];
int I[MAXN];
int Sol[MAXN];

    int cmp(muchie A, muchie B)
    {
        return A.c < B.c;
    }
    
    int father(int nod)
    {
        while (T[nod])
          nod = T[nod];
        
        return nod;
    }

    int main()
    {
        freopen(FIN,"r",stdin);
        freopen(FOUT,"w",stdout);
        
        scanf("%d%d",&N,&M);
        for (i = 1; i <= M; ++i)
           scanf("%d%d%d",&H[i].x,&H[i].y,&H[i].c);
        
        sort(H + 1, H + M + 1, cmp);
        
        cost = ct = 0;
        
        int par1, par2;
        for (i = 1; i <= M; ++i)
           {
              par1 = father(H[i].x);
              par2 = father(H[i].y);
              
              if (par1 != par2)
                 {
                    if (I[par1] == I[par2])
                      I[par2]++;
                    if (I[par1] <= I[par2])
                      T[par1] = par2;
                    else
                      T[par2] = par1;
                    cost += H[i].c;
                    Sol[++ct] = i;
                 }
           }
        
        printf("%d\n%d\n",cost, N-1);
        for (i = 1; i <= ct; ++i)
           printf("%d %d\n",H[Sol[i]].x, H[Sol[i]].y);
        
        return 0;
    }