#include <cstdio>
#include <algorithm>
using namespace std;
struct MUCHIE{int x,y,c;}mu[400001];
int rad[200001];
int dru[200001];
int ct,n,m;
bool compmu(MUCHIE a, MUCHIE b)
{
    return (a.c<=b.c);
}
int gas(int a)
{
    int pa=a,aux;
    for(;rad[pa]!=0;pa=rad[pa]);
    for(;a!=pa;aux=rad[a],rad[a]=pa,a=aux);
    return pa;
}
bool raddif(int a, int b)
{
    int ra=gas(a),rb=gas(b);
    if(ra!=rb)
        rad[ra]=rb;
    return (ra!=rb);
}
void kru()
{
    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 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);
    kru();
    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;
}