#include <fstream>
#include <algorithm>
using namespace std;
#define NMAX 200005
#define NMAX2 400005
int t[NMAX],n,m,rez,sol[NMAX][2];
ifstream fin("apm.in");
ofstream fout("apm.out");
int tata(int nod)
{
    if(t[nod] == 0)
        return nod;
    int r = tata(t[nod]);
    t[nod] = r;
    return r;
}
struct data{
    int cost,x,y;
};
data v[NMAX2];
bool cmp(data a,data b)
{
    return a.cost < b.cost;
}
void tipar()
{
    for(int i=1;i<=m;i++)
        fout<<v[i].cost<<" ";
}
int main()
{
    int cod,x,y,a,b,c,pas=0;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v[i].cost=c;
        v[i].x = x;
        v[i].y = y;
    }
    sort(v+1,v+m+1,cmp);
    //tipar();
    for(int i=1;i<=m;i++)
    {
        a=tata(v[i].x);
        b=tata(v[i].y);
        if(a==b)
            continue;
        t[b]=a;
       // fout<<v[i].x<<" "<<a<<" "<<v[i].y<<" "<<b<<endl;
        rez+=v[i].cost;
        pas++;
        sol[pas][0]=v[i].x;
        sol[pas][1]=v[i].y;
        if(pas==n-1) break;
    }
    fout<<rez<<"\n"<<n-1<<"\n";
    for(int i=1;i<n;i++)
        fout<<sol[i][0]<<" "<<sol[i][1]<<"\n";
}