#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)
{
    if (component[node] == node)
        return node;
    component[node] = get_grade(component[node]);
    return component[node];
}

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

    for (int i = 1; i <= M; ++i)
    {
        int gradeX = get_grade(edge[i].x);
        int gradeY = get_grade(edge[i].y);
        if ( gradeX != gradeY )
        {
            final_cost += edge[i].cost;
            component[gradeX] = gradeY;
            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;
}