#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin ("apm.in");
ofstream fout ("apm.out");

#define MAXN 200050
#define MAXM 400050

struct edge_w_cost {
    int x, y, cost;
};

vector <edge_w_cost> solution_edge;
int component[MAXN], final_cost;
edge_w_cost stream, edge[MAXM];

int N, M;

int sort_by_cost (edge_w_cost a, edge_w_cost b)
{
    return a.cost < b.cost;
}

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

int get_grade (int node)
{
    while (component[node] != node)
        node = component[node];
    return node;
}

void kruskal_algorithm()
{
    sort(edge+1, edge+M+1, sort_by_cost);

    for (int i = 1; i <= M; ++i)
    {
        if ( get_grade(edge[i].x) != get_grade(edge[i].y) )
        {
            final_cost += edge[i].cost;
            component[get_grade(edge[i].x)] = get_grade(edge[i].y);
            solution_edge.push_back(edge[i]);
        }
    }

    fout <<final_cost <<'\n' <<N-1 <<'\n';
    for (int i = 0; i < solution_edge.size(); ++i)
        fout <<solution_edge[i].x <<' ' <<solution_edge[i].y <<'\n';

}

int main()
{
    fin >>N >>M;
    initialize_component(N);
    for (int i = 1; i <= M; ++i)
    {
        fin >>edge[i].x >>edge[i].y >>edge[i].cost;
    }

    kruskal_algorithm();

    return 0;
}