#include <fstream>
#include <iostream>
#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];
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;
}


bool cmp(edge a1,edge a2){return (a1.c<a2.c);}


int main()
{
    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;



    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;
            v[a]=b;
            if(lg>=(n-1))   break;
        }
    }


    printf("%d\n%d\n", cost, lg);
    for(i=1;i<n;i++){
        printf("%d %d\n",tree[sol[i]].x,tree[sol[i]].y);
    }

}