// Alg Cormen
#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define Inf 0x3f3f3f3f

int N, M;
// daca retin graful asa, nu pot gasi usor costul mst
vector<vector<pair<int, int> > > G;
vector<int> key, t; // key[v] - muchia usoara care leaga nodul de arbore
set<pair<int, int> > T;
set<pair<int, int> >::iterator it;
vector<bool> inQ;
vector<pair<int, int>> apm;
int cost_mst;

// Alg Cormen
void Prim()
{
    int ke, u, v, w;
    key[1] = 0;
    T.insert( mp(0, 1) ); inQ[1] = true;
    for(int i = 2; i <= N; i++)
        key[i] = Inf, T.insert(mp(key[i], i));

    while ( !T.empty() )
    {
        ke = T.begin()->first, u = (*T.begin()).second;
        T.erase(T.begin());

        for(auto p : G[u] )
        {
			v = p.first;
			w = p.second; // costul muchiei
			it = T.find(mp(key[v], v));
			if( it != T.end() && key[v] > w )
			{
                T.erase(it);
				key[v] = w;
				t[v] = u;
                T.insert(mp(w, v)); // nu mai inserez noduri duplicate
            }
		}
    }
}

int main(void)
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    int i, a, b, c;

    scanf("%d %d", &N, &M);
 	G.resize(N + 1);   t.resize(N + 1);
	key.resize(N + 1); inQ.resize(N + 1);

   for(i = 1; i <= M; i++)
        scanf("%d %d %d\n", &a, &b, &c),
        G[a].pb(mp(b, c)),
        G[b].pb(mp(a, c));

    Prim();
	int edges = 0;
    for(i = 2; i <= N; i++)
        for (const auto& x : G[i])
            if ( x.first == t[i] )
            {
                cost_mst += x.second;
                apm.push_back({x.first, i});
                edges++;
                break;
			}
  
    printf("%d\n%d\n", cost_mst, N - 1);
    for (const auto& e : apm)
		printf("%d %d\n", e.first, e.second);

    return 0;
}