#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

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

struct Edge
{
    int a;
    int b;
    int cost;
};

bool cmp(const Edge& a, const Edge& b)
{
    return a.cost < b.cost;
}

int n, m;
vector <Edge> edges;
int fathers[200005];
int depth[200005];
vector <Edge> ans;


int FindRoot(int node)
{
    if (fathers[node] == node)
    {
        return node;
    }
    return fathers[node] = FindRoot(fathers[node]);
}

void Union(int a, int b)
{
    a = FindRoot(a);
    b = FindRoot(b);

    if (depth[a] == depth[b])
    {
        depth[a]++;
        fathers[b] = a;
    }
    else if (depth[a] < depth[b])
    {
        fathers[a] = b;
    }
    else
    {
        fathers[b] = a;
    }
}


int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        fathers[i] = i;
        depth[i] = 1;
    }

    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;
        Edge newEdge = {a, b, c};
        edges.push_back(newEdge);
    }

    sort(edges.begin(), edges.end(), cmp);

    for (Edge edge : edges)
    {
        if (FindRoot(edge.a) == FindRoot(edge.b))
        {
            continue;
        }
        Union(edge.a, edge.b);
        ans.push_back(edge);
    }

    int cost = 0;
    for (Edge edge : ans)
    {
        cost += edge.cost;
    }

    fout << cost << '\n';
    fout << ans.size() << '\n';
    for (Edge edge : ans)
    {
        fout << edge.a << ' ' << edge.b << '\n';
    }
}