#include <cstdio>
#include <algorithm>
#define buff_size 400001
using namespace std;
int v[200001],n,m,t,a,b,aux,i,cost=0,lg=0,sol[400001],sz[200001];
struct edge {int x;int y;int c;} tree[400001];
char buff[buff_size];int pos=0, semn;
FILE*f=freopen("apm.in","r",stdin);
FILE*g=freopen("apm.out","w",stdout);
inline void read(int &nr){
    semn = 1;
    while(buff[pos] < '0' || buff[pos] > '9'){if(buff[pos]== '-' )semn = -1; if(++pos == 200000) fread(buff, 1, 200000, stdin), pos = 0;}
    nr = 0;
    while('0' <= buff[pos] && buff[pos] <= '9') {nr = nr * 10 + buff[pos] - '0';if(++pos == 200000) fread(buff, 1, 200000, stdin), pos = 0;}
    nr*=semn;
}


struct cmp{   bool operator () (edge a,edge b) { return a.c<b.c; }};
char buffw[buff_size]="";int posw;
void write(int a, int b){

    posw += sprintf(buffw + posw,"%d %d\n", a, b);
    if(lg > buff_size) fwrite(buffw, buff_size , 1, stdout), posw = 0;
}

int main()
{   fread(buff, 1, 200000, stdin);
    read(n);read(m);

    for(i=1; i<=m; ++i)   read(tree[i].x),read(tree[i].y),read(tree[i].c);
    sort(tree+1,tree+1+m,cmp());
    for(i=1; i<=n; ++i) v[i]=i,sz[i]=1;



    for(i=1;i<=m;i++)
    {
        a=tree[i].x;while(a!=v[a]) aux=v[v[a]],v[a]=aux,a=aux;
        b=tree[i].y;while(b!=v[b]) aux=v[v[b]],v[b]=aux,b=aux;

        if(a!=b)
        {
            cost+=tree[i].c;
            sol[++lg]=i;
           if(sz[a]<sz[b]) v[a]=b,sz[b]+=sz[a];
           else v[b]=a,sz[a]+=sz[b];
            if(lg>=(n-1))   break;
        }
    }


    posw= sprintf(buffw + posw, "%d\n%d\n", cost, lg);
    for(i=1;i<n;i++){
        write(tree[sol[i]].x,tree[sol[i]].y);
    }
    fwrite(buffw, posw, 1, stdout);
}