#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct muchie
{
    int x,y;
    int cost;
};
const int NMAX=200005;
const int MMAX=400005;
ifstream si("apm.in");
ofstream so("apm.out");
muchie v[MMAX];
int tata[NMAX];
bool luat[MMAX];

int radacina(int x)
{
    while(tata[x]!=tata[tata[x]])
        tata[x]=tata[tata[x]];
    return tata[x];
}

bool alipire(int x,int y)
{
    int tx=radacina(x),ty=radacina(y);

    if(tx!=ty)
    {
        tata[tx]=ty;
        return true;
    }

    return false;
}

bool comp(muchie a,muchie b)
{
    return a.cost<b.cost;
}

int main()
{
    int n,m;

    si>>n>>m;

    int i;
    for(i=1;i<=n;++i)
        tata[i]=i;
    for (i=0;i<m;++i)
        si>>v[i].x>>v[i].y>>v[i].cost;

    sort(v,v+m,comp);

    int cost=0;
    for(i=0;i<m;++i)
    {
        if(alipire(v[i].x,v[i].y))
        {
            cost+=v[i].cost;
            luat[i]=true;
        }
    }
    so<<cost<<'\n'<<n-1<<'\n';
    for(i=0;i<m;++i)
        if(luat[i])
            so<<v[i].y<<' '<<v[i].x<<'\n';
    so.close();
    return 0;
}