#include <bits/stdc++.h>
#define pb push_back
using namespace std;

const int Dim = 400001;

int N,M,Sol,Idx[Dim],S[Dim],X[Dim],Y[Dim],W[Dim];
vector< int > E;

bool Compare(int A,int B)
{
    return (W[A] < W[B]);
}

int Find(int X)
{
    if (S[X] == X)
        return X;

    S[X] = Find(S[X]);

    return S[X];
}

void Union(int X,int Y)
{
    S[Find(X)] = Find(Y);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);

     scanf("%d %d\n",&N,&M);

     for (int i = 1;i <= N;i++)
        S[i] = i;

     for (int i = 1;i <= M;i++)
     {
         scanf("%d %d %d\n",&X[i],&Y[i],&W[i]);
         Idx[i] = i;
     }

     sort(Idx + 1,Idx + M + 1,Compare);

     for (int i = 1;i <= M;i++)
     {
         if (Find(X[Idx[i]]) != Find(Y[Idx[i]]))
         {
             Sol += W[Idx[i]];
             Union(X[Idx[i]],Y[Idx[i]]);
             E.pb(Idx[i]);
         }
     }

     printf("%d\n%d\n",Sol,N - 1);

     for (int i = 0;i < N - 1;i++)
        printf("%d %d\n",X[E[i]],Y[E[i]]);

  return 0;
}