#include<bits/stdc++.h>
using namespace std;

const int N_MAX = 400005;

struct muchie{int x, y, cost;}vec[N_MAX];
int tata[N_MAX], viz[N_MAX], h[N_MAX], N, M, s, ct;

inline bool cmp(muchie x, muchie y)
{ return x.cost < y.cost; }

void read()
{
    ifstream f("apm.in");

    f >> N >> M;
    for(int i = 1; i <= M; i ++)
        f >> vec[i].x >> vec[i].y >> vec[i].cost;

    f.close();
}

void initialize()
{
    for(int i = 1; i <= N; i++)
    {  tata[i] = i; h[i] = 1;  }
}

int find_set(int x)
{
    if( x == tata[x] )
        return x;
    else return tata[x] = find_set(tata[x]);
}

void Union( int u, int t )
{
    int tata_u, tata_t;
    tata_u = find_set(u); tata_t = find_set(t);
    if( h[tata_u] > h[tata_t] )
    {
        tata[tata_t] = tata_u;
    }else{
        tata[tata_u] = tata_t;
        if( h[u] == h[t] ) h[t] ++;
    }
}

void solve()
{
    sort( vec+1, vec+M+1, cmp );

    for(int i = 1; i <= M; i++)
        if( find_set(vec[i].x) != find_set(vec[i].y) )
        {
            s += vec[i].cost;
            Union(vec[i].x, vec[i].y);
            viz[i] = 1; ct ++;
            if( ct == N-1 ) break;
        }
}

void write()
{
    ofstream out("apm.out");

    out << s << "\n" << N-1 <<"\n";
    for(int i = 1; i <= N; i ++)
        if( viz[i] == 1 )
            out << vec[i].x <<" " << vec[i].y <<"\n";

    out.close();
}

int main()
{
    read();
    initialize();
    solve();
    write();
    return 0;
}