#include <bits/stdc++.h>
using namespace std;
ifstream fin ("apm.in");
ofstream fout ("apm.out");
struct muchie
{
    int x;
    int y;
    int c;
};
int cmp (muchie a, muchie b)
{
    return a.c<b.c;
}
pair <int, int > sol[400001];
muchie a[400001];
int n, m, i, t[100001], cost, dim;
int rad (int nod)
{
    int start=nod;
    while (t[nod]>0)
        nod=t[nod];
    if (nod!=start)
        t[start]=nod;
    return nod;
}
int main ()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
        fin>>a[i].x>>a[i].y>>a[i].c;
    sort (a+1, a+m+1, cmp);
    for (i=1; i<=m; i++)
    {
        int rx=rad(a[i].x);
        int ry=rad(a[i].y);
        if (rx!=ry)
        {
            ///punem muchia si le unim
            if (-t[rx]==-t[ry])
            {
                ///inaltimile sunt egale, marim inaltimea cu 1 si unim ry cu rx
                t[ry]=rx;
                t[rx]--;
            }
            else if (-t[rx]>-t[ry])
                t[ry]=rx;
            else
                t[rx]=ry;
            sol[++dim].first=a[i].x;
            sol[dim].second=a[i].y;
            cost+=a[i].c;
            if (dim==n-1)
                break;
        }
    }
    fout<<cost<<"\n"<<dim<<"\n";
    for (i=1; i<=dim; i++)
        fout<<sol[i].first<<" "<<sol[i].second<<"\n";
}