#include <fstream>
#include <algorithm>
using namespace std;
ifstream fi("apm.in");
ofstream g("apm.out");
#define f first
#define s second
#define mp make_pair
#define nmax 400002
#define asd 200002
pair<int , pair<int,int> > v[nmax];
int t[asd],what[asd],man[asd];
typedef long long ll;
ll ct;
bool use[nmax];
int father(int x)
{
    while(t[x])
        x=t[x];
    return x;
}
int main()
{
    int n,m,i,j,x,y,xx,yy,cx,cy,tx,ty,c,cou=0;
    fi>>n>>m;
    for(i=1;i<=m;i++)
    {
        fi>>x>>y>>c;
        v[i]=mp(c,mp(x,y));
    }
    sort(v+1,v+m+1);
    for(i=1;i<=m;i++)
    {
        tx=father(v[i].s.f);
        ty=father(v[i].s.s);
        if(tx!=ty)
        {
            use[i]=1;
            cou+=1;
            xx=v[i].s.f;
            yy=v[i].s.s;
            ct+=ll(v[i].f);
            if(man[tx]>=man[ty])
            {
                if(man[tx]==man[ty])
                    man[tx]+=1;
                while(yy)
                {
                    cy=t[yy];
                    t[yy]=tx;
                    yy=cy;
                }
            }
            else
                {
                    while(xx)
                    {
                        cx=t[xx];
                        t[xx]=ty;
                        xx=cx;
                    }
                }
        }
    }
    g<<ct<<'\n';
    g<<cou<<'\n';
    for(i=1;i<=m;i++)
        if(use[i]==1)
            g<<v[i].s.f<<" "<<v[i].s.s<<'\n';
    return 0;
}