#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)
{
    if(a.c<b.c)
        return true;
    return false;
}
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)
    {
        tata[s2]=s1;
        nr++;
        w[nr].i=x;
        w[nr].j=y;
        cost+=c;

    }
}
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+n+1,cmp);
    gata=0;
    for(i=1;i<=m && !gata;i++)
    {
        unire(v[i].x,v[i].y,v[i].c);
        if(nr==n-1)
            gata=1;
    }
    out<<cost<<'\n'<<nr<<'\n';
    for(i=1;i<=nr;i++)
        out<<w[i].i<<' '<<w[i].j<<'\n';
    return 0;
}