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

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

const int MAXN = 200005;
typedef pair<int, int> cuplu;

struct triplu {
    int from, to, cost;
};

struct cmp {
    bool operator()(const triplu &A, const triplu &B) const {
        return A.cost > B.cost;
    }
};

vector<cuplu> G[MAXN];
vector<cuplu> Edges;
priority_queue<triplu, vector<triplu>, cmp> PQ;
int N, M, Sol;
bool marked[MAXN];

void Read() {
    fin >> N >> M;
    int a, b, c;
    for (int i = 0; i < M; ++i) {
        fin >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
        G[b].push_back(make_pair(a, c));
    }
}

void Prim() {
    PQ.push({0, 1, 0});
    do {
        triplu node = PQ.top();
        PQ.pop();
        if (marked[node.to] == true) continue;
        marked[node.to] = true;
        Sol += node.cost;
        if (node.from != 0)
            Edges.push_back(make_pair(node.from, node.to));
        vector<cuplu>::iterator it;
        for (it = G[node.to].begin(); it != G[node.to].end(); ++it) {
            if (marked[it->first] == false)
                PQ.push({node.to, it->first, it->second});
        }
    }while (!PQ.empty() && Edges.size() < N - 1);
}

void Write() {
    fout << Sol << '\n';
    fout << Edges.size() << '\n';
    vector<cuplu>::iterator it;
    for (it = Edges.begin(); it != Edges.end(); ++it)
        fout << it->first << ' ' << it->second << '\n';
}

int main() {
    Read();
    Prim();
    Write();
    fin.close();
    fout.close();
    return 0;
}