#include <fstream>
#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);
ofstream g("apm.out");
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; }};

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;



    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;
        }
    }


    g<<cost<<'\n'<<lg<<'\n';
    for(i=1;i<n;i++){
        g<<tree[sol[i]].x<<' '<<tree[sol[i]].y<<'\n';
    }

}