#include <bits/stdc++.h>

using namespace std;

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

int rang[400005] , t[400005] , n , m , cnt;
long long s;

struct muchie
{
    int x , y , c;
}v[400005],afi[400005];

bool cmp(muchie a , muchie b)
{
    if(a.c < b.c)
    return true;
    else
        if(a.c == b.c && a.x < b.x)
        return true;
    return false;
}

int radacina ( int nod)
{
    if(t[nod] == 0)
        return nod;
    else
    {
        int k = radacina(t[nod]);
        t[nod] = k;
        return k;
    }
}

void unire(int a , int b)
{
    int ra = radacina(a);
    int rb = radacina(b);

    if(rang[ra] > rang[rb])
        t[ra] = rb;
    else
        t[rb] = ra;

    if(rang[ra] < rang[rb])
        rang[rb]++;

}

int main()
{
    f >> n >> m;

    for ( int i = 1; i <= m ; i++)
    {
        f >> v[i].x >> v[i].y >> v[i].c;
    }

    sort ( v + 1 , v + m + 1 , cmp);

    for ( int i = 1 ; i <= m ; i++)
    {
        int a = v[i].x , b = v[i].y , cost = v[i].c;
        if(radacina(a) != radacina(b))
        {
            s = s + cost;
            cnt++;
            afi[cnt] = v[i];;
            unire(a,b);
        }
    }
    g << s << '\n';
    g << cnt << '\n';
    for ( int i = 1 ; i <= cnt ; i++)
             g << afi[i].x << " " << afi[i].y << '\n';
}