#include <algorithm>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

#define FORIT(it, v) for (typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)

struct EDGES {
    int x, y, c;
};


const int N = 200005;
const int INF = 0x3f3f3f3f;

int n, m, ans_cost;
int cost[N], father[N];
bool viz[N];
vector <pair <int, int> > graph[N], ans_edge;

struct cmp {
    bool operator () (const int &a, const int &b) {
        return cost[a] > cost[b];
    }
};

priority_queue <int, vector <int>, cmp > heap;

void inApm(int top) {
    viz[top] = true;
    FORIT(it, graph[top]) {
        if (!viz[it->first] && it->second < cost[it->first]) {
            father[it->first] = top;
            cost[it->first] = it->second;
        }
    }
}

void init(int n) {
    for (int i = 1; i <= n; ++i)
        cost[i] = INF;

    cost[1] = 0;
    
    inApm(1);

    for (int i = 2; i <= n; ++i)
        heap.push(i);
}

int main() {
    f >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        graph[x].push_back(make_pair(y, c));
        graph[y].push_back(make_pair(x, c));
    }

    init(n);

    while (!heap.empty()) {
        int top = heap.top();
        heap.pop();
       
        inApm(top);
        ans_cost += cost[top];
        ans_edge.push_back(make_pair(top, father[top]));
        
        //inApm(top);
    }

    g << ans_cost << '\n';
    g << ans_edge.size() << '\n';
    FORIT(it, ans_edge)
        g << it->first << ' ' << it->second << '\n';
}