#include <fstream>
#include <algorithm>

using namespace std;

const int N = 200001;
const int M = 400001;

struct muchii
{
    int n1;
    int n2;
    int cost;
} v[M], aux;

int t[N];

bool cmp(muchii x, muchii y)
{
    return (x.cost < y.cost);
}

int rad (int x)
{
    if (t[x]==0)
        return x;
    t[x]=rad(t[x]);
    return t[x];
}

void reun (int x, int y)
{
    int rx=rad(x);
    int ry=rad(y);
    if (rx!=ry)
        t[ry]=rx;
}

bool verif (int x, int y)
{
    return (rad(x)==rad(y));
}

int main()
{
    ifstream in ("apm.in");
    ofstream out ("apm.out");
    int n, m, tip, x,y, ctotal=0;
    bool selectat[N];
    in>>n>>m;
    for (int i=1; i<=m; i++)
        in>>v[i].n1>>v[i].n2>>v[i].cost;
    /*
    for (int i=1; i<=m; i++)
    {
        for (int j=i+1; j<=m; j++)
        {
            if (v[i].cost>v[j].cost)
            {
                aux=v[i];
                v[i]=v[j];
                v[j]=aux;
            }
        }
    }
    */
    sort(v + 1, v + m + 1, cmp);
    for (int i=1; i<=m; i++)
    {
        if (!verif(v[i].n1, v[i].n2))
        {
            ctotal += v[i].cost;
            selectat[i] = true;
            reun(v[i].n1, v[i].n2);
        }
    }
    out<<ctotal<<"\n"<<n-1<<"\n";
    for (int i=1; i<=m; i++)
    {
        if (selectat[i]==true)
            out<<v[i].n1<<" "<<v[i].n2<<"\n";
    }
    return 0;
}