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

std::vector <int> mst_edges;

struct edge
{
    int u, v, w;
} edges[400001];

int parent[200001];

int cmp(edge e1, edge e2)
{
    return (e1.w < e2.w);
}
int find(int x)
{
    if (parent[x] == x) return x;
    parent[x] = find(parent[x]);
    return parent[x];
}
void merge(int x, int y)
{
    parent[find(x)] = find(y);
}

int main()
{
    std::ifstream fin("apm.in");
    std::ofstream fout("apm.out");

    int n, m, total_cost = 0;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> edges[i].u >> edges[i].v >> edges[i].w;

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

    std::sort(edges + 1, edges + m + 1, cmp);

    for (int i = 1; i <= m; i++)
        if (find(edges[i].u) != find(edges[i].v))
        {
            total_cost += edges[i].w;
            merge(edges[i].u, edges[i].v);
            mst_edges.push_back(i);
        }
    

    fout << total_cost << "\n";
    fout << n - 1 << "\n";
    for (int i = 0; i < n - 1; i++)
        fout << edges[mst_edges[i]].v << " " << edges[mst_edges[i]].u << "\n";
    
    return 0;
}