#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream g("apm.out");
#define mp make_pair
#define f first
#define s second
pair < int, pair< int,int > > v[400003];
bool use[400003];
#define nmax 200010
typedef long long ll;
int t[nmax],cate[nmax];
int father(int x)
{
    while(t[x])
        x=t[x];
    return x;
}
int main()
{
    int i,n,m,x,cx,muchii=0,y,cost,tx,ty;
    ll costtotal=0;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>cost;
        v[i]=mp(cost,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)
        {
            costtotal+=ll(v[i].f);
            muchii+=1;
            use[i]=1;
            x=v[i].s.f;
            while(t[x])
            {
                cx=x;
                x=t[x];
                t[cx]=tx;
            }
            if(cate[tx]==cate[ty])
            {
                cate[tx]+=1;
                t[ty]=tx;
            }
            else
                if(cate[tx]>cate[ty])
                {
                    t[ty]=tx;
                }
                else
                    t[tx]=ty;
        }
    }
    g<<costtotal<<'\n'<<muchii<<'\n';
    for(i=1;i<=m;i++)
    {
        if(use[i]==1)
            g<<v[i].s.f<<" "<<v[i].s.s<<'\n';
    }
    return 0;
}