#include <fstream>
#include <algorithm>
#define Nmax 200002
using namespace std;
ifstream cin("apm.in");
ofstream cout("apm.out");

struct ura{
    int x,y,cost,used;
} e[2*Nmax];
int n,m,i,c,nr;
int sef[Nmax],v[Nmax];
bool cmp(ura a,ura b)
{
    return a.cost<b.cost;
}
int sefsuprem(int x)
{
    if(sef[x]==x)
        return x;
    int r=sefsuprem(sef[x]);
    sef[x]=r;
    return r;
}
void unire(int x,int y)
{
    int sefx=sefsuprem(x),sefy=sefsuprem(y);
    if(sefx!=sefy)
    {
        nr++;
        e[i].used=1;
        c+=e[i].cost;
        if(v[sefx]>v[sefy])
            sef[sefy]=sefx;
        else
        {
            sef[sefx]=sefy;
            if(v[sefx]==v[sefy])
                v[sefy]++;
        }
    }
}
int main()
{
    cin>>n>>m;
    for (i=1;i<=m;i++)
        cin>>e[i].x>>e[i].y>>e[i].cost;
    for (i=1;i<=n;i++)
        sef[i]=i;
    sort(e+1,e+m+1,cmp);
    for(i=1;i<=m;i++)
        unire(e[i].x,e[i].y);
    cout<<c<<'\n'<<nr<<'\n';
    for(i=1;i<=m;i++)
        if(e[i].used==1)
            cout<<e[i].x<<" "<<e[i].y<<"\n";

    return 0;

}