//Vasilut
#include<fstream>
#include<algorithm>
#include<utility>

#define NN 400001
#define mp make_pair
#define f first
#define s second

using namespace std;
ofstream out("apm.out");


int n,m,poz[NN],T[NN],sum,sol;
pair< pair< int, int >, int > v[NN];

void read();
void prep();
int find(int x);
void unite(int x ,int y);
void kruskal();
void write_sol();
bool cmp( pair< pair< int, int > , int  > i, pair<  pair< int, int  >, int > j )
{
        return i.s < j.s ;
}


int main()
{
    read();
    sort(v+1,v+m+1,cmp);
    kruskal();
    write_sol();
    return 0;
}


void read()
{
    ifstream in("apm.in");
    in>>n>>m;
    for (int x,y,c,i=1;i<=m;i++)
    {
        in>>x>>y>>c;
        v[i]=mp( mp(x,y) , c ) ;
    }
}

void prep()
{
    for(int i=1;i<=n;i++)
        T[i] = i;
}

int find( int x )
{
    if ( x != T[x] )
        return T[x] = find( T[x] );
    return x;
}

void unite( int x ,int y)
{
    int m1,m2;
    m1 = find(x);
    m2 = find(y);
    T[m2] = m1;
}


void kruskal()
{
    prep();
    pair < pair <int , int > , int > I;
    for(int i=1;i<=m;i++)
    {
        I= v[i];
        int x = (I.f).f;
        int y = (I.f).s;
        int c = I.s;
        if ( find( x ) != find( y ) )
        {
            ++sol;
            poz[sol] = i;
            sum += c;
            unite ( x , y );
        }
    }
}

void write_sol()
{
    out<<sum<<'\n';
    out<<sol<<'\n';
    for(int i=1 ; i<=sol; ++i)
        out << (v[poz[i]].f).f << " " <<(v[poz[i]].f).s << " " <<'\n';
}