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

using namespace std;


struct muchie
{
    int x,y,c,*t=0,ok = 0;
    muchie(int X,int Y,int C)
    {
        x = X;
        y = Y;
        c = C;
    }
};

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

struct nod
{
    int value;
    int rang;
    nod *parent = this;
}*nodes[200005];
int K;

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(pb->rang>pa->rang)
        pa->parent = pb;
    else
    {
        pb->parent = pa;
        pa->rang ++;
    }
}

int N,M;
vector<muchie> v;

int nr,cost;
int main()
{
    freopen("apm.in","r",stdin);
    freopen("apm.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1; i<=M; i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        v.push_back(muchie(x,y,c));
    }
    for(int i=1; i<=N; i++)
    {
        nodes[i] = new nod;
        nodes[i] -> value=i;
    }
    sort(v.begin(),v.end(),comp);


    for(vector<muchie>::iterator ii = v.begin(); ii!=v.end(); ii++)
    {
        int x = ii->x;
        int y = ii->y;
        int c = ii->c;
        if(find(nodes[x])==find(nodes[y]))
            continue;
        merge(nodes[x],nodes[y]);
        nr++;
        cost+=c;
        ii->ok =1;

    }
    printf("%d\n%d\n",cost,nr);
    for(vector<muchie>::iterator ii = v.begin(); ii!=v.end(); ii++)
    {
        if(ii->ok)
            printf("%d %d\n",ii->y,ii->x);
    }
    return 0;
}