#include<stdio.h>
#include<algorithm>
using namespace std;
struct Muchie {
    int x;
    int y;
    int val;
};
struct NodTree {
    int x;
    int y;
};
Muchie sir[400005];
int Sum;
int ord[400005];
int N;
NodTree Tree[200005];
int M;
int P[200005];
int sel;
int R[200005];
bool cmpf(int i, int j)
{
    return sir[i].val < sir[j].val;
}
int FindSet(int x)
{
    if (x != P[x]) P[x] = FindSet(P[x]);
    return P[x];
}
void Union(int x,int y)
{
    int r1 = FindSet(x);
    int r2 = FindSet(y);
    if (r1 != r2)
     {
         if (R[r1] > R[r2]) P[r2] = r1;
          else
          {
              P[r1] = r2;
              if (R[r1] == R[r2]) R[r2]++;

          }
     }
}

int main()
{
        freopen("apm.in","r",stdin);
        freopen("apm.out","w",stdout);
        scanf("%d %d",&N, &M);
        for(int i = 1; i <= M; i++)
         {
             scanf("%d %d %d",&sir[i].x,&sir[i].y,&sir[i].val);
             ord[i] = i;
         }
        for(int i = 1; i <= N; i++)
         P[i] = i;
        sort(ord + 1, ord + M + 1, cmpf);
        for(int i = 1; sel < N - 1; i++)
         {
             int r1 = FindSet(sir[ord[i]].x);
             int r2 = FindSet(sir[ord[i]].y);
             if (r1 != r2)
              {
                  sel++;
                  Tree[sel].x = sir[ord[i]].x;
                  Tree[sel].y = sir[ord[i]].y;
                  Sum+= sir[ord[i]].val;
                  Union(r1,r2);
              }

         }
        printf("%d\n%d\n",Sum,N-1);
        for(int i = 1; i <= sel; i++)
         printf("%d %d\n",Tree[i].y,Tree[i].x);
        return 0;

}