#include<cstdio>
#include<algorithm>
using namespace std;
struct muchie {int x,y,c;} G[400005];
int n,m,k,cost,L[200005],A[200005];
void citire()
{
    int i;
    scanf("%d%d",&n,&m);
    for (i=1;i<=m;++i)
        {
            scanf("%d%d%d",&G[i].x,&G[i].y,&G[i].c);
            L[i]=i;
        }
}
int cmp(muchie a1, muchie a2)
{
    if (a1.c<a2.c) return 1;
    else return 0;
}
void kruskal()
{
    int i=1,j,nr1,nr2;
    while (k<n-1)
        {
            if (L[G[i].x]!=L[G[i].y])
                {
                    cost+=G[i].c;
                    A[++k]=i;
                    nr1=L[G[i].x], nr2=L[G[i].y];
                    for (j=1;j<=n;++j)
                        if (L[j]==nr2) L[j]=nr1;
                }
            ++i;
        }
}
void afis()
{
    int i;
    printf("%d\n%d\n",cost,n-1);
    for (i=1;i<n;++i)
        printf("%d %d\n",G[A[i]].x,G[A[i]].y);
}
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    sort(G+1,G+m+1,cmp);
    kruskal();
    afis();
    return 0;
}