#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
ifstream in("apm2.in");
ofstream out("apm2.out");

#define inf 1e9

struct Muchie {
    int x, y, dist;

    Muchie() {}
    Muchie(int x, int y, int dist) : x(x), y(y), dist(dist) {}
};
struct Node {
    int x, dist;
    Node() {}
    Node(int x, int dist) : x(x), dist(dist) {}
};
bool operator<(const Muchie &a, const Muchie &b) {
    if (a.dist == b.dist) {
        return a.x > b.x;
    }
    return a.dist > b.dist;
}

typedef vector<vector<Node>> ListaVecini;

// Pentru LCA
int timer = 0;
int log_n;
vector<pair<int,int>> euler;
vector<Node> tata;
vector<int> depth;
vector<vector<Node>> lca;

void createEuler(int node, int parent, ListaVecini &vecini) {
    euler[node].first = timer;
    timer++;

    for (const Node& vec : vecini[node]) {
        if (vec.x == parent)
            continue;
        tata[vec.x] = Node(node, vec.dist);
        depth[vec.x] = depth[node] + 1;
        createEuler(vec.x, node, vecini);
    }

    euler[node].second = timer;
    timer++;
}
bool areAncestors(int x, int y) {
    return (euler[x].first <= euler[y].first && euler[y].second <= euler[x].second) ||
           (euler[y].first <= euler[x].first && euler[x].second <= euler[y].second);
}
void createLCA(int n, int log_n) {

    for (int i = 0; i < n; i++) {
        lca[i][0] = tata[i];
    }

    for (int j = 1; j < log_n; j++)
        for (int i = 0; i < n; i++) {
            lca[i][j].x = lca[lca[i][j-1].x][j-1].x;
            lca[i][j].dist = max(lca[i][j-1].dist, lca[lca[i][j-1].x][j-1].dist);
        }
}
int findCommonAncestor(int x, int y) {
    if (areAncestors(x, y)) {
        if (depth[x] < depth[y])
            return x;
        return y;
    }

    int j = log_n - 1;

    while (j >= 0) {
        while (j >=0 && areAncestors(lca[x][j].x, y))
            j--;
        if (j < 0)
            break;
        x = lca[x][j].x;
        j--;
    }

    return lca[x][0].x;
}
int getMaxFromTo(int x, int y) {
    if (!areAncestors(x, y)) {
        cout << "ERROR: Should be ancestors" << endl;
        throw(exception());
    }
    if (x == y)
        return -1;

    int Max = 0;
    int j = log_n - 1;

    while (j >= 0) {
        while (j >= 0 && depth[lca[x][j].x] < depth[y])
            j--;
        if (j < 0)
            break;

        Max = max(Max, lca[x][j].dist);
        x = lca[x][j].x;
        j--;

        if (x == y)
            break;
    }
    if (x != y) {
        cout << "ERROR: Ar trebui sa fie egale" << endl;
    }

    return Max;
}
int maxMuchieBetween(int x, int y) {
    int anc = findCommonAncestor(x, y);

    return max(getMaxFromTo(x, anc), getMaxFromTo(y, anc));
}

vector<Muchie> Prim(int n, const ListaVecini &vecini) {

    vector<Muchie> rasp;
    priority_queue<Muchie> pq;
    vector<bool> visited(n, false);

    visited[0] = true;
    for (const Node& v : vecini[0]) {
        if (visited[v.x])
            continue;
        pq.emplace(0, v.x, v.dist);
    }

    while (!pq.empty() && rasp.size() < n - 1) {
        Muchie p = pq.top();
        
        pq.pop();

        if (visited[p.x] && visited[p.y])
            continue;

        int nod = p.y;
        if (visited[p.y])
            nod = p.x;

        visited[nod] = true;
        rasp.push_back(p);

        for (const Node& v : vecini[nod]) {
            if (visited[v.x])
                continue;
            pq.emplace(nod, v.x, v.dist);
        }
    }

    return rasp;
}

int main() {

    int n, m, q;
    in >> n >> m    ;
    ListaVecini vecini(n);
    for (int i = 0; i < m; i++) {
        Muchie k;
        in >> k.x >> k.y >> k.dist;
        k.x--; k.y--;
        vecini[k.x].emplace_back(k.y, k.dist);
        vecini[k.y].emplace_back(k.x, k.dist);
    }


    vector<Muchie> apm = Prim(n, vecini);
    int cost = 0;
    for (const Muchie& v : apm)
        cost += v.dist;
    out << cost << "\n";
    out << n - 1 << "\n";
    for (const Muchie& v : apm)
        out << v.x + 1 << " " << v.y + 1 << "\n";
    return 0;
    ListaVecini apmVecini(n);

    for (int i = 0; i < n - 1; i++) {
        apmVecini[apm[i].x].emplace_back(apm[i].y, apm[i].dist);
        apmVecini[apm[i].y].emplace_back(apm[i].x, apm[i].dist);
    }


    // Start Initializari LCA
    euler.assign(n, make_pair(0, 0));
    tata.assign(n, Node());
    depth.assign(n, 0);
    tata[0] = Node(0, -1);

    createEuler(0, -1, apmVecini);
    log_n = ceil(log(n));

    lca = vector<vector<Node>> (n, vector<Node> (log_n));
    createLCA(n, log_n);
    // End Initializari LCA

    for (int querry = 0; querry < q; querry++) {
        int x, y; in >> x >> y;
        x--; y--;
        out << maxMuchieBetween(x, y) - 1 << "\n";
    }
    return 0;
}