#include <fstream>
#include <vector>
#include <algorithm>
#define pb push_back
#define f first
#define mp make_pair
#define M 400005
#define N 200005

struct s
{
    int n1, n2, muchii;
} v[M];

using namespace std;

ifstream cin("apm.in");
ofstream cout("apm.out");


vector < s > sol;
vector < vector < pair < int, int > > > G;
int stramos[N], raspuns;
int n, m;

bool comp(s a, s b)
{
    return a.muchii < b.muchii;
}

int tata(int x)
{
    if(stramos[x] == x)
        return x;
    stramos[x] = tata(stramos[x]);

    return stramos[x];
}

void reuniune(int x, int y)
{
    stramos[tata(x)] = tata(y);
}

void citire()
{
    cin >> n >> m;
    G.resize(n + 5);

    for(int i = 1 ; i <= m ; i++)
    {
        cin >> v[i].n1 >> v[i].n2 >> v[i].muchii;
        G[v[i].n1 ].pb(mp(v[i].n2, v[i].muchii) );
        G[v[i].n2 ].pb(mp(v[i].n1, v[i].muchii) );
    }


}

void prep()
{
    sort(v + 1, v + m + 1, comp);

    for(int i = 1 ; i <= n ; i++)
        stramos[i] = i;
}

void rez()
{


    for(int i = 1 ; i <= m ; i++)
        if(tata(v[i].n1) != tata(v[i].n2))
    {
        raspuns += v[i].muchii, reuniune(v[i].n1, v[i].n2),
        sol.pb(v[i]);
    }

}

void afis()
{
    cout << raspuns << '\n' << sol.size() << '\n';
    for(int i = 0 ; i < sol.size() ; i++)
        cout << sol[i].n1 << ' ' << sol[i].n2 << '\n';
}

int main()
{
    citire();
    prep();
    rez();
    afis();
    return 0;
}