#include<cstdio>
#include<stdlib.h>
#include<algorithm>

using namespace std;

struct camp
{
       int a, b;
       }u[1000],a[1000];

int m,n,cost[1000],ind[1000],viz[1000],ct,k,ct1;
int cmp(int i, int j)
{
    return cost[i] < cost[j];
}


int main()
{int i,j;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    
    scanf("%d%d",&n,&m);
    
    for (i = 1; i <= m; i++)
    {
        scanf("%d%d%d",&u[i].a,&u[i].b,&cost[i]);
        ind[i] = i;
        }
        
    sort(ind + 1, ind + m + 1, cmp);
    
    for (i = 1; i <= n; i++)
    viz[i] = 0;
    
    viz[u[ind[1]].a] = 1;
    viz[u[ind[1]].b] = 1;
    
    a[1] = u[ind[1]];
    ct = cost[ind[1]];
    
    ct1 = 1;
    for (k = 1; k <= n - 2; k++)
    {
          i = 1;
          while (viz[u[ind[i]].a] == 1 && viz[u[ind[i]].b] == 1) i++;
          a[i] = u[ind[i]];
          ct1++;
          if (viz[u[ind[i]].a]) viz[u[ind[i]].b] = 1;
                          else  viz[u[ind[i]].a] = 1;
                                                               
          ct += cost[ind[i]];
          
          }
    printf("%d\n",ct);
    printf("%d\n",ct1);
    for (i = 1; i <= ct1; i++)
    {
        printf("%d %d",a[i]);
        printf("\n");
        }
return 0;
}