#include<algorithm>
#include<iostream>
#include<fstream>
#include<vector>
#include<set>
#define DN 200010
using namespace std;
fstream fin("apm.in",ios::in),fout("apm.out",ios::out);
struct strv
{
    int x,y,c;
    bool operator < (const strv &b) const
    {
        return c<b.c;
    }
};
vector<strv> v,r;
int t[DN],n,m;
int tata(int nod)
{
    if(t[nod]==nod) return nod;
    return t[nod]=tata(t[nod]);
}

int main()
{
    int i,j,tx,ty,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        v.push_back({x,y,c});
    }
    for(i=1;i<=n;i++) t[i]=i;
    sort(v.begin(),v.end());
    c=0;
    for(auto j:v)
    {
        if(r.size()==n-1) break;

        tx=tata(j.x);
        ty=tata(j.y);
        if(tx!=ty)
        {
            c+=j.c;
            t[tx]=ty;
            r.push_back(j);
        }
    }
    fout<<c<<"\n";
    fout<<n-1<<"\n";
    for(auto j:r)
    {
        fout<<j.x<<" "<<j.y<<"\n";
    }
}