#include<fstream>
#include<algorithm>

struct Muchie {
    int x;
    int y;
    int val;
};
struct NodTree {
    int x;
    int y;
};
Muchie sir[400005];
NodTree Tree[200005];
int ord[400005],P[200005],R[200005],sel,Sum,n, M;



bool cmparaCost(int i, int j)
{
    return sir[i].val < sir[j].val;
}
int FindSet(int x)
{
    if (x != P[x]) P[x] = FindSet(P[x]);
    return P[x];
}
void Union(int x,int y)
{
    int r1 = FindSet(x);
    int r2 = FindSet(y);
    if (r1 != r2)
    {
        if (R[r1] > R[r2])
            P[r2] = r1;
        else
        {
            P[r1] = r2;
            if (R[r1] == R[r2])
                R[r2]++;

        }
    }
}

int main()
{

    std::ifstream f ("apm.in");
    std::ofstream g ("apm.out");
    f>>n>>M;
    for(int i = 1; i <= M; i++)
    {
        f>>sir[i].x>>sir[i].y>>sir[i].val;
        ord[i] = i;
    }
    for(int i = 1; i <= n; i++)
        P[i] = i;
    std::sort(ord + 1, ord + M + 1, cmparaCost);
    for(int i = 1; sel < n - 1; i++)
    {
        int r1 = FindSet(sir[ord[i]].x);
        int r2 = FindSet(sir[ord[i]].y);
        if (r1 != r2)
        {
            sel++;
            Tree[sel].x = sir[ord[i]].x;
            Tree[sel].y = sir[ord[i]].y;
            Sum+= sir[ord[i]].val;
            Union(r1,r2);
        }

    }

    g<<Sum<<std::endl<<n-1<<std::endl;
    for(int i = 1; i <= sel; i++)
        g<<Tree[i].x<<Tree[i].y<<std::endl;
    return 0;

}