#include <fstream>
#include <algorithm>

#define N 400004
using namespace std;

ifstream f("apm.in");
ofstream fout("apm.out");
struct muchie
{
    int x, y, c;
}G[N];

int cost, muchii, Rx, Ry, n, m;
int r[N], rang[N], sol[N];

bool cond(muchie x, muchie y)
{
    return (x.c<y.c);
}

int root(int x)
{
    while(r[x])
        x=r[x];
    return x;
}
void Kruskal()
{
    for(int i=1; i<=m; i++)
        rang[i]=1;
    for(int i=1; i<=m && muchii<n-1; i++)
    {
        Rx=root(G[i].x);
        Ry=root(G[i].y);
        if(Rx!=Ry)
        {
            cost+=G[i].c;
            sol[++muchii]=i;

            if(rang[Rx]>rang[Ry])
            {
                rang[Rx]=rang[Rx]+rang[Ry];
                r[Ry]=Rx;
            }
            else
            {
                rang[Ry]=rang[Ry]+rang[Rx];
                r[Rx]=Ry;
            }
        }
    }
}
int main()
{
    f >> n >> m;
    for(int i=1; i<=m; i++)
        f >> G[i].x >> G[i].y >> G[i].c;
    sort(G+1, G+1+m, cond);
    Kruskal();
    fout << cost << endl << n-1 << endl;
    for(int i=1; i<n; i++)
        fout << G[sol[i]].x << " " << G[sol[i]].y << " " << endl;
    return 0;
}