#include<stdlib.h>
#include<cstdio>
#include<algorithm>
using namespace std;

struct camp
{
       int x,y;
       }u[1000],a[1000];
int cost[1000],ind[1000],comp[1000],nr1,nr2,k,n,ct,m;
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].x,&u[i].y,&cost[i]);
        ind[i] = i;
        }
    
    for (i = 1; i <= n; i++)
    comp[i] = i;
    
    sort(ind + 1, ind + m + 1, cmp);
    
    k = 0; i = 1; int ct1 = 0;
    while (k < n - 1)
    {
        if (comp[u[ind[i]].x] != comp[u[ind[i]].y])
        {
        k++;
        a[++ct1] = u[ind[i]];
        ct = ct + cost[ind[i]];
        nr1 = comp[u[ind[i]].x]; nr2 = comp[u[ind[i]].y];
        
        for (j = 1; j <= n; j++)
        if (comp[j] == nr2) comp[j] = nr1;
        }
    i++;
    }
    printf("%d",ct);
    printf("\n");
    printf("%d",ct1);
    printf("\n");
    for (i = 1; i <= ct1; i++)
    {
        printf("%d %d ",a[i].x,a[i].y);
        printf("\n");
        }
return 0;
}