#include <algorithm>
#include<cstdio>

using namespace std;

#define DMAX 400005

struct muchie{
    int x;
    int y;
    int val;
};muchie M[DMAX];

int ind;

int n,m,h[DMAX],tata[DMAX],use[DMAX],cate,sol[DMAX];

void citire()
{
    freopen("apm.in","rt",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&M[i].x,&M[i].y,&M[i].val);
}

void quickSort(int left, int right)
{
      int i = left, j = right;
      muchie tmp;
      muchie pivot = M[(left + right) / 2];
      while (i <= j)
      {
            while (M[i].val < pivot.val)
                  i++;
            while (M[j].val > pivot.val)
                  j--;
            if (i <= j)
            {
                  tmp = M[i];
                  M[i] = M[j];
                  M[j] = tmp;
                  i++;
                  j--;
            }
      }
      if (left < j)
            quickSort(left, j);
      if (i < right)
            quickSort(i, right);
}
int Find(int x)
{
    int r=x,aux;
    while(tata[r]!=0)
    {
        r=tata[r];
    }
    while(tata[x]!=0)
    {
        aux=tata[x];
        tata[x]=r;
        x=aux;
    }
    return r;
}
void Union(int a, int b)
{
    if(h[a]>h[b])
    {
        tata[b]=a;
    }
    else
        if(h[b]>h[a])
        {
            tata[a]=b;
        }
        else
        {
            tata[b]=a;
            h[a]++;
        }
}
void afisare()
{
    int s=0;
    freopen("apm.out","wt",stdout);
    for(int i=1;i<=ind;i++)
            s+=M[sol[i]].val;
    printf("%d\n%d\n",s,cate);
    for(int i=1;i<=ind;i++)
            printf("%d %d\n",M[sol[i]].x,M[sol[i]].y);
}
int main()
{
    citire();
    quickSort(1,m);
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x=Find(M[j].x);
            int y=Find(M[j].y);
            if(x!=y&&use[j]==0)
            {
                use[j]=1;
                ind++;
                sol[ind]=j;
                cate++;
                Union(x,y);
                break;
            }
        }
    }
    afisare();
    return 0;
}