#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
vector <int> VANS;
int GR[400005],X[400005],Y[400005],C[400005],IND[400005],N,M,i,ANS;
bool cmp(int a,int b) {return C[a]<C[b];}
int grupa(int x)
{
    if (GR[x]==x) return x;
    GR[x]=grupa(GR[x]);
    return GR[x];
}
void reuniune(int x,int y)
{
    GR[grupa(x)]=grupa(y);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d %d",&N,&M);
    for (i=1;i<=M;i++) scanf("%d %d %d",&X[i],&Y[i],&C[i]),IND[i]=i;
    for (i=1;i<=N;i++) GR[i]=i;
    sort(IND+1,IND+M+1,cmp);
    for (i=1;i<=M;i++)
    {
        if (grupa(X[IND[i]])!=grupa(Y[IND[i]]))
        {
            ANS+=C[IND[i]];
            reuniune(X[IND[i]],Y[IND[i]]);
            VANS.pb(IND[i]);
        }
    }
    printf("%d\n%d\n",ANS,N-1);
    for (i=0;i<N-1;i++)
        printf("%d %d\n",X[VANS[i]],Y[VANS[i]]);
    return 0;
}