#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

const int maxn = 400100;
int C[maxn];
//int GR[maxn],X[maxn],Y[maxn],
//int N,M,ANS,IND[maxn];
//vector<int> VANS;

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

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

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

int main()
{
    int GR[maxn],X[maxn],Y[maxn];//,C[maxn];
    int N,M,ANS,IND[maxn];
    vector<int> VANS;
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d\n",&N,&M);
    for(int i = 1;i <= M;++i)
    {
        scanf("%d %d %d\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,cmpf);
    for(int i = 1;i <= M; ++i)
    {
        if (grupa(X[IND[i]],GR) != grupa(Y[IND[i]],GR)){
            ANS += C[IND[i]];
            reuniune(X[IND[i]],Y[IND[i]],GR);
            VANS.push_back(IND[i]);
        }
    }
    printf("%d\n",ANS);
    printf("%d\n",N - 1);
    for(int i = 0;i < N - 1; ++i)
        printf("%d %d\n",X[VANS[i]],Y[VANS[i]]);
    return 0;
}