//
//  main.cpp
//  apm
//
//  Created by Razvan Vranceanu on 06/02/2020.
//  Copyright © 2020 Razvan Vranceanu. All rights reserved.
//

#include <fstream>
#include <algorithm>
#define M_MAX 400001
#define N_MAX 200001
using namespace std;
ifstream f("apm.in");
ofstream g("apm.out");

int n, m, t[N_MAX], cost_min, poz;

struct muchie
{
    int x, y, cost;
} x[M_MAX], traseu[M_MAX];

void citire()
{
    f>>n>>m;
    for(int i=1;i<=m;i++)
        f>>x[i].x>>x[i].y>>x[i].cost;
}

int compare(muchie m1, muchie m2)
{
    return m1.cost < m2.cost;
}
void reunire(int t[M_MAX], muchie m1)
{
    int ai=t[m1.x];
    int aj=t[m1.y];
    for(int j =1 ; j <= n ; ++j)
        if(t[j] == aj)
            t[j] = ai;
}
int main()
{
    citire();
    sort(x+1, x+m+1, compare);
    //completare t
    for(int i =1 ; i <= n ; ++i)
        t[i] = i;
    for(int i=1;i<=m;i++)
        if(t[x[i].x] != t[x[i].y] ) //extremitatile fac parte din subrabori diferiti
        {
            cost_min+=x[i].cost;
            reunire(t, x[i]);
            traseu[++poz]=x[i];
        }
    g<<cost_min<<'\n';
    g<<poz<<'\n';
    for(int i=1;i<=poz;i++)
        g<<traseu[i].x<<" "<<traseu[i].y<<'\n';
    return 0;
}