#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 grupa(int nr)
{
    if (L[nr]==nr) return nr;
    L[nr]=grupa(L[nr]);
    return L[nr];
}
void reun(int nr1, int nr2)
{
    L[grupa(nr1)]=grupa(nr2);
}
int cmp(muchie a1, muchie a2)
{
    if (a1.c<a2.c) return 1;
    else return 0;
}
void kruskal()
{
    int i=1,nr1,nr2;
    while (k<n-1)
        {
            nr1=G[i].x, nr2=G[i].y;
            if (grupa(nr1)!=grupa(nr2))
                {
                    cost+=G[i].c;
                    A[++k]=i;
                    reun(nr1,nr2);
                }
            ++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;
}