#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>

#define NMAX 200005
#define MMAX 400005
using namespace std;

int N,M;
int used[MMAX];
int cost,nr;
struct nod
{
    int rang;
    int value;
    nod *parent = this;
}*nodes[NMAX];

struct muchie
{
    int a,b,c;

}graf[MMAX];

bool comp(muchie a,muchie b)
{
    return a.c < b.c;
}

nod* find(nod *&x)
{
    if(x->parent != x)
        x->parent = find(x->parent);
    return x->parent;
}

void merge(nod *&a, nod *&b)
{
    nod *pa = find(a);
    nod *pb = find(b);

    if(pa->rang > pb->rang)
        pb->parent = pa;
    else if(pa->rang < pb->rang)
        pa->parent = pb;
    else
    {
        pb->parent = pa;
        pa->rang++;
    }
}

void citire()
{
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {

        scanf("%d%d%d",&graf[i].a,&graf[i].b,&graf[i].c);
    }
    for(int i=1;i<=N;i++)
    {
        nodes[i] = new nod;
        nodes[i] -> rang = 1 ;
    }
}

void rezolva()
{
    sort(graf+1,graf+M+1,comp);
    for(int i=1;i<=M;i++)
    {
        if(find(nodes[graf[i].a])==find(nodes[graf[i].b]))
            continue;
        merge(nodes[graf[i].a],nodes[graf[i].b]);
        cost += graf[i].c;
        nr++;
        used[i]=1;
    }
    printf("%d\n%d\n",cost,nr);
    for(int i=1;i<=M;i++)
        if(used[i])
            printf("%d %d\n",graf[i].a,graf[i].b);
}

int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    citire();
    rezolva();
    return 0;
}