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

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


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

bool cmp(const Edge& other1, const Edge& other2)
{
    return other1.cost < other2.cost;
}

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


int FindRoot(int a)
{
    if (a == father[a])
    {
        return a;
    }
    return father[a] = FindRoot(father[a]);
}

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

    if (depth[a] == depth[b])
    {
        depth[a]++;
        father[b] = a; 
    }
    else if (depth[a] > depth[b])
    {
        father[b] = a;
    }
    else
    {
        father[a] = b;
    }
}


int main()
{
    fin >> n >> m;
    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 (int i = 0; i < n; i++)
    {
        father[i] = i;
        depth[i] = 1;
    }
    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.b << ' ' << edge.a << '\n';
    }
}