#include <fstream>
#include <algorithm>

using namespace std;
ifstream in("apm.in");
ofstream out("apm.out");
struct ceva
{
    int x,y,c;
}v[400001];
struct altceva
{
    int i,j;
}w[200001];
int tata[200001],nr,cost;

bool cmp(ceva a, ceva b)
{
    return a.c<b.c;
}
int sef(int x)
{
    if(tata[x]==x)
        return x;
    else
        return tata[x]=sef(tata[x]);
}
void unire(int x, int y, int c)
{
    int s1=sef(x);
    int s2=sef(y);
    if(s1!=s2)
    {
        cost+=c;
        nr++;
        w[nr].i=x;
        w[nr].j=y;
        tata[s2]=s1;

    }
}
int main()
{
    int n,m,i,gata;
    in>>n>>m;
    for(i=1;i<=m;i++)
        in>>v[i].x>>v[i].y>>v[i].c;

    for(i=1;i<=n;i++)
        tata[i]=i;

    sort(v+1,v+m+1,cmp);

    gata=0;
    for(i=1;i<=m && !gata;i++)
        unire(v[i].x,v[i].y,v[i].c);

    out<<cost<<'\n'<<nr<<'\n';

    for(i=1;i<=nr;i++)
        out<<w[i].i<<' '<<w[i].j<<'\n';
    return 0;
}