#include <cstdio>
#include <ctime>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define FORIT(it,v) for(typeof((v).begin())it=(v).begin();it!=(v).end();++it)
ifstream fin("apm.in");
ofstream fout("apm.out");
const int MAX_N = 200100;
const int MAX_M = 400100;

int N, M;
vector<int> graph[MAX_N];
bool visited[MAX_N];
struct Edge {
    int node1, node2, cost;
    int other_node(int node) {
        return node1 + node2 - node;
    }
    int free_node() {
        if (visited[node1] == false) return node1;
        if (visited[node2] == false) return node2;
        return 0;
    }
    friend istream& operator >> (istream &in, Edge &e) {
        return in >> e.node1 >> e.node2 >> e.cost;
    }
    friend ostream& operator << (ostream& out, Edge &e) {
        return out << e.node1 << ' ' << e.node2 << '\n';
    }
    bool operator< (const Edge& other) const {
        return cost > other.cost;
    }
} edges[MAX_M];
int solCost;
vector<Edge> solEdges;

void read_input(), solve(), print_output();

int main() {
    read_input();
    solve();
    print_output();
}

void read_input() {
    fin >> N >> M;
    for (int i = 1; i <= M; ++i) {
        fin >> edges[i];
        graph[edges[i].node1].push_back(i);
        graph[edges[i].node2].push_back(i);
    }
}

void solve() {
    srand(time(NULL));
    
    priority_queue<Edge> heap;
    int start_node = rand() % N + 1;
    visited[start_node] = true;
    FORIT (it, graph[start_node])
        heap.push(edges[*it]);

    while (!heap.empty()) {
        Edge e;
        int current_node;
        do {
            e = heap.top();
            heap.pop();
            current_node = e.free_node();
        } while (!heap.empty() && current_node == 0);
        if (current_node == 0) break;

        solCost += e.cost;
        solEdges.push_back(e);
        
        visited[current_node] = true;
        FORIT (it, graph[current_node]) {
            if (!visited[edges[*it].other_node(current_node)]) {
                heap.push(edges[*it]);
            }
        }
    }
}

void print_output() {
    fout << solCost << '\n';
    fout << solEdges.size() << '\n';
    FORIT (it, solEdges) {
        fout << *it;
    }
}