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

struct edge {
    int weight, startpoint, endpoint;
};


class Compare {
    public:
        bool operator() (edge a, edge b) {
            return a.weight > b.weight;
        }
};

int n, m;
long long cm;
bool selected[200001];
vector<edge> g[200001];
vector<edge> apm;
priority_queue<edge, vector<edge>, Compare> q;

void citire();
void afisare();
void Prim(int x);




int main() {

    citire();
    Prim(1);
    afisare();

    return 0;
}


void Prim(int start_node) {
    edge e;
    e.weight = 0;
    e.endpoint = start_node;
    q.push(e);

    while (!q.empty()) {
        e = q.top();  q.pop();
        int x = e.endpoint;

        if (selected[x]) continue;

        cm += e.weight;
        apm.push_back(e);
        selected[x] = true;

        for (int i = 0; i < g[x].size(); ++i) {
            if (!selected[g[x][i].endpoint]) {
                g[x][i].startpoint = x;
                q.push(g[x][i]);
            }
        }
    }
}

bool compare(edge a, edge b) {
    return a.weight < b.weight;
}

void afisare() {
    ofstream out("apm.out");

    out << cm << '\n';
    out << apm.size() - 1 << '\n';

    for (int i = 1; i < apm.size(); ++i) {
        out << apm[i].startpoint << " " << apm[i].endpoint << '\n';
    }

    out.close();
}

void citire() {
    ifstream in("apm.in");
    int x, y, c;
    edge e;

    in >> n >> m;
    for (int i = 1; i <= m; ++i) {
        in >> x >> y >> c;
        e.weight = c;
        e.endpoint = y;
        g[x].push_back(e);
        e.endpoint = x;
        g[y].push_back(e);
    }

    in.close();
}