#include<stdio.h>
#include<algorithm>
using namespace std;
struct Muchie {
     int x;
     int y;
     int cost;
};
Muchie a[200005];
int n;
int sum;
int nrM;
int prt[400005];
int ord[200005];
int rank[200005];
int p[200005];
int m;
void Union(int x, int y)
{
    if (rank[x] > rank[y])
      p[y] = x;
     else
      {
          if (rank[x] == rank[y]) rank[y]++;
          p[x] = y;
      }
}
int FindSet(int x)
{
    if (x != p[x])
     p[x] = FindSet(p[x]);
    return p[x];
}

bool cmpf(int i, int j)
{
    return (a[i].cost < a[j].cost);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

    scanf("%d %d",&n,&m);
    for(int i = 1; i <= n; i++)
     p[i] = i;
    for(int i = 1; i <= m; i++)
     {
      scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].cost);
      p[i] = i;
      ord[i] = i;
     }
    sort(ord + 1, ord + m + 1, cmpf);
    for(int i = 1; nrM < n-1; i++)
     {
         int r1 = FindSet(a[ord[i]].x);
         int r2 = FindSet(a[ord[i]].y);
         if (r1 != r2)
          {
              nrM++;
              prt[++prt[0]] = a[ord[i]].x;
              prt[++prt[0]] = a[ord[i]].y;
              sum += a[ord[i]].cost;
              Union(r1,r2);
          }
     }
    printf("%d \n",sum);
    printf("%d \n",nrM);
    for(int i = 1; i <= 2 * nrM; i+=2)
     printf("%d %d\n",prt[i],prt[i+1]);
    return 0;
}