#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

#define maxn 200001
#define maxm 400001

int n,m,i,j,x1,yy,c1,cost,rez,k,nr,q;

struct costuri{
    int x,y,c;
};

costuri muchie[maxm];
int T[maxn],rang[maxn];
bool ok[maxn];
int sol[maxm][2];

inline bool cmp (const costuri &a, const costuri &b)
{
    return a.c<b.c;
}

inline int multime (int nod)
{
    if (T[nod]!=nod)
        T[nod]=multime(T[nod]);
    return T[nod];
}

void reuneste(int i,int j)
{
    i=multime(i);
    j=multime(j);
    if (i==j) return;
    if (rang[i]<rang[j])
        T[i]=j;
    else T[j]=i;
    if (rang[i]==rang[j])
        rang[i]++;
}

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",&x1,&yy,&c1);
        muchie[i].x=x1;
        muchie[i].y=yy;
        muchie[i].c=c1;
    }
    sort(muchie+1,muchie+m+1,cmp);
    for (i=1;i<=n;i++)
    {
        T[i]=i;
        rang[i]=0;
    }
    memset(ok,false,sizeof(ok));
    q=0;
    for (k=1;k<=m;k++)
    {
        i=muchie[k].x;
        j=muchie[k].y;
        cost=muchie[k].c;
        if (multime(i)!=multime(j))
        {
            reuneste(i,j);
            rez+=cost;
            q++;
            sol[q][0]=i;
            sol[q][1]=j;
        }
    }
    printf("%d\n",rez);
    printf("%d\n",q);
    for (i=1;i<=q;i++)
        printf("%d %d\n",sol[i][0],sol[i][1]);
    return 0;
}