#include <iostream>
#include <fstream>
using namespace std;

ifstream in("apm.in");
ofstream out("apm.out");

struct muchie {int nx;
                int ny;
                int cost;};
muchie m[400001],r[200001];
int n,o,p[400001],suma,muchi=0;
int parinte(int nod)
{
    if(p[nod]==nod)
        return nod;
    return p[nod]=parinte(p[nod]);
}
void unite(int x,int y)
{
    p[parinte(x)]=parinte(y);
}
bool cmp(muchie a,muchie b)
{
    return a.cost<b.cost;
}

int main()
{
    in>>n>>o;
    for(int i=1;i<=o;i++)
        in>>m[i].nx>>m[i].ny>>m[i].cost;
    for(int i=1;i<o;i++)
    {
        for(int j=i+1;j<=o;j++)
        {
            int r=cmp(m[i],m[j]);
            if(r==0)
            {
                swap(m[i],m[j]);
            }
        }
    }
    int i=1;
    while(muchi<n-1)
    {
        if(!p[m[i].nx])
            p[m[i].nx]=m[i].nx;
        if(!p[m[i].ny])
            p[m[i].ny]=m[i].ny;
        int px=parinte(m[i].nx);
        int py=parinte(m[i].ny);
        if(px!=py)
        {
            unite(m[i].nx,m[i].ny);
            suma=suma+m[i].cost;
            muchi++;
            r[muchi]=m[i];
        }
        i++;
    }
    out<<suma<<'\n'<<muchi<<'\n';
    for(int j=1;j<=muchi;j++)
        out<<r[j].nx<<' '<<r[j].ny<<'\n';
    return 0;
}