#include <cstdio>
#include <algorithm>
using namespace std;
typedef struct{int x,y,c;}MUCHIE;
MUCHIE mu[400001];
int rad[400001];
int dru[400001];
int ct;
bool compmu(MUCHIE a, MUCHIE b)
{
    if(a.c<b.c)
        return 1;
    return 0;
}
int gas(int a)
{
    int pa=a,rf,aux;
    while(pa!=rad[pa])
        pa=rad[pa];
    rf=pa;
    pa=a;
    while(pa!=rad[pa])
    {
        aux=rad[pa];
        rad[pa]=rf;
        pa=aux;
    }
    return rf;
}
bool raddif(int a, int b)
{
    int ra,rb;
    ra=gas(a);
    rb=gas(b);
    if(ra!=rb)
    {
        rad[ra]=rb;
        return 1;
    }
    return 0;
}
void kru(int m)
{
    int i;
    sort(mu+1,mu+m+1,compmu);
    for(i=1;i<=m;i++)
        if(raddif(mu[i].x,mu[i].y))
        {
            dru[0]++;
            dru[dru[0]]=i;
            ct+=mu[i].c;
        }
}
int main()
{
    int n,m,i;
    freopen("apm.in","r",stdin);
    scanf("%d %d\n",&n,&m);
    for(i=1;i<=m;i++)
        scanf("%d %d %d\n",&mu[i].x,&mu[i].y,&mu[i].c);
    fclose(stdin);
    for(i=1;i<=n;i++)
        rad[i]=i;
    kru(m);
    freopen("apm.out","w",stdout);
    printf("%d\n%d\n",ct,dru[0]);
    for(i=1;i<=dru[0];i++)
        printf("%d %d\n",mu[dru[i]].x,mu[dru[i]].y);
    fclose(stdout);
    return 0;
}