#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

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

pair < int, pair < int , int > > v[400005];
pair < int, int> rsp[200005];

int i, a, b, c, pa[200005], sum, n, m, cnt;

int dsu ( int nod )
{
    if ( pa[nod] == nod )
    {
        return nod;
    }

    return pa [ nod ] = dsu ( pa[nod] );

}

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

    for ( i = 1; i <= m ; i++ )
    {
        f>>a>>b>>c;

        v[i].x = c;
        v[i].y.x = a;
        v[i].y.y = b;

    }

    for ( i = 1; i <= n ; i++ )
    {
        pa[i] = i;
    }

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

    for ( i = 1; i <= m ; i++ )
    {
        if ( dsu ( v[i].y.x ) != dsu ( v[i].y.y ) )
        {
            sum += v[i].x;;
            rsp[++cnt] = { v[i].y.x , v[i].y.y };
            pa [ dsu ( v[i].y.y ) ] = pa [ dsu ( v[i].y.x ) ];
        }
    }

    g<<sum;

    g<<'\n'<<cnt<<'\n';

    for ( i = 1; i <= cnt ; i++ )
    {
        g<<rsp[i].x<<" "<<rsp[i].y<<'\n';
    }

    return 0;
}