#include <bits/stdc++.h>
#define endl '\n'

using namespace std;

const string fileName = "apm";
ifstream in  (fileName + ".in");
ofstream out (fileName + ".out");

const int maxcSize = 102;
const int inf = 0x3f3f3f3f;

int parent[maxcSize], cSize[maxcSize];
int findParent(int node) {
    while (node != parent[node]) node = parent[node];
    return node;
}

bool connect(int nodeA, int nodeB) {
    nodeA = findParent( nodeA );
    nodeB = findParent( nodeB );

    if (nodeA == nodeB) return false;

    if (cSize[nodeA] < cSize[nodeB]) swap(nodeA, nodeB);
    cSize[nodeA] += cSize[nodeB]; parent[nodeB] = nodeA;
    return true;
}

struct type {int nodeA, nodeB, cost;};

bool cmpFunction(type a, type b) {
    if (a.cost == b.cost) {
        if (a.nodeA == b.nodeA) return a.nodeB < b.nodeB;
        return a.nodeA < b.nodeA;
    }
    return a.cost < b.cost;
}
vector <type> edges;
vector <pair <int , int>> toShow;
int main( ) {
    int numNodes, numEdges; in >> numNodes >> numEdges;

    type curr; edges.reserve(numEdges + 1);
    for (int i = 0; i < numEdges; ++i) {
        in >> curr.nodeA >> curr.nodeB >> curr.cost;
        edges.emplace_back(curr);
    }
    sort(edges.begin( ), edges.end( ), cmpFunction);

    for (int i = 1; i <= numNodes; ++i) {
        parent[i] = i; cSize[i] = 1;
    }

    int ans = 0; toShow.reserve(numNodes);
    for (auto edge : edges) {
        if (toShow.size( ) == numNodes - 1) break;
        if (connect(edge.nodeA, edge.nodeB)) {
            toShow.emplace_back(edge.nodeA, edge.nodeB);
            ans += edge.cost;
        }
    }

    out << ans << endl;
    out << toShow.size( ) << endl;
    for (auto edge : toShow) out << edge.first << ' ' << edge.second << endl;
    return 0;
}