#include <cstdio>

#define MAX_N 200002
#define MAX_M 400004

int X[MAX_M], Y[MAX_M], C[MAX_M], TT[MAX_N], RG[MAX_N], SOL[MAX_N];
int N, M, K, Cs;

void Swap(int i, int j)
{
     X[i] ^= X[j] ^= X[i] ^= X[j];
     Y[i] ^= Y[j] ^= Y[i] ^= Y[j];
     C[i] ^= C[j] ^= C[i] ^= C[j];
}

void HeapUp(int k)
{
     if(k <= 1) return;
     
     int t = k >> 1;
     
     if(C[t] < C[k])
     {
             Swap(t, k);
             HeapUp(t);
     }
}

void Restore(int r, int b)
{
     if(r << 1 <= b)
     {
          int st = r << 1, dr;
          if( (r << 1) + 1 <= b ) dr = (r << 1) + 1;
          else
              dr = st - 1;
              
          int x = C[st] > C[dr] ? st : dr;
          
          if(C[x] > C[r])
          {
                  Swap(r, x);
                  Restore(x, b);
          }
     }
}

int Parinte(int nd)
{
    int R = nd;
    while(TT[R] != R)
                R = TT[R];
                
    while(TT[nd] != R)
    {
                 int x = TT[nd];
                 TT[nd] = R;
                 nd = x;
    }

    return R;
}

int main()
{
    freopen("apm.in", "rt", stdin);
    freopen("apm.out", "wt", stdout);

    int i;    
    for ( scanf("%d %d", &N, &M), i = 1; i <= M; ++i )
        scanf("%d %d %d", X+i, Y+i, C+i);
        
    for ( i = 2; i <= M; ++i )
        HeapUp(i);

    for( i = M; i > 1; --i )
    {
         Swap(1, i);
         Restore(1, i-1);
    }

    for ( i = 1; i <= N; ++i )
    {
        TT[i] = i;
        RG[i] = 1;
    }
    
    for ( i = 1; i <= M; ++i )
    {
        int t, s;
        t = Parinte(X[i]);
        s = Parinte(Y[i]);
        
        if(t != s)
        {
             Cs += C[i];
             SOL[++K] = i;
             
             if(RG[t] < RG[s])
                      TT[t] = s;
             else
                 TT[s] = t;
                 
             if(RG[t] == RG[s])
                      ++ RG[t];
        }
    }

    printf("%d\n%d\n", Cs, K);

    for ( i = 1; i <= K; ++i )
        printf("%d %d\n", X[SOL[i]], Y[SOL[i]]);

    fclose(stdin);
    fclose(stdout);
    return 0;
}