#include<cstdio>
#include<algorithm>
#include<vector>
#define pb push_back

using namespace std;

const int maxn = 400100;

int GR[maxn],X[maxn],Y[maxn],C[maxn];
int N,M,cost,IND[maxn];
vector<int> VANS;

/*int grupa(int i)
{
    if (GR[i] == i) return i;
    GR[i] = grupa(GR[i]);
    return GR[i];
}

void reuniune(int i,int j)
{
    GR[grupa(i)] = grupa(j);
}*/

void reuniune(int i,int j)
{
    int k=GR[i];
    for(i=1;i<=N;i++)
        if(GR[i]==k)
            GR[i]=GR[j];
}

bool comp(int i,int j)
{
    return(C[i] < C[j]);
}

int main()
{
    FILE *f=fopen("apm.in","r"),*g=fopen("apm.out","w");
    fscanf(f,"%i %i\n",&N,&M);
    for(int i = 1;i <= M;++i)
    {
        fscanf(f,"%i %i %i\n",&X[i],&Y[i],&C[i]);
        IND[i] = i;
    }

    for(int i = 1;i <= N; ++i) GR[i] = i;
    sort(IND + 1,IND + M + 1,comp);
    for(int i = 1;i <= M; ++i)
    {
        if (GR[X[IND[i]]] != GR[Y[IND[i]]]){
            cost+= C[IND[i]];
            reuniune(X[IND[i]],Y[IND[i]]);
            VANS.pb(IND[i]);
        }
    }
    fprintf(g,"%i\n",cost);
    fprintf(g,"%i\n",N - 1);
    for(int i = 0;i < N - 1; ++i)
        fprintf(g,"%i %i\n",X[VANS[i]],Y[VANS[i]]);
    return 0;
}