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

int enr = 0, n, m, sum = 0;

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

// Edge struct to represent edges in the graph
struct Edge {
    int from, to, weight;
};

vector<vector<Edge>> adj;

// Comparison function for min-heap
struct comp {
    bool operator() (const Edge &a, const Edge &b) {
        return a.weight > b.weight;
    }
};

// Function to implement Prim's algorithm
vector<Edge> prim() {
    vector<Edge> mst; // vector to store the MST
    vector<bool> visited(n + 1, false); // vector to keep track of visited vertices
    priority_queue<Edge, vector<Edge>, comp> pq; // min-heap

    // Starting vertex
    int start = 1;
    visited[start] = true;

    // Adding all edges from the starting vertex to the min-heap
    for (Edge e : adj[start]) {
        pq.push(e);
    }

    // Loop until MST is obtained
    while (!pq.empty()) {
        Edge e = pq.top();
        pq.pop();

        // Checking if the edge's vertices are already in the MST
        if (visited[e.to]) {
            continue;
        }

        // Adding the edge to the MST
        mst.push_back(e);
        enr++;
        sum += e.weight;

        // Finding the next vertex to visit
        int v = e.to;
        visited[v] = true;

        // Adding all edges from the next vertex to the min-heap
        for (Edge edge : adj[v]) {
            if (!visited[edge.to]) {
                pq.push(edge);
            }
        }
    }

    return mst;
}
int main()
{
    fin >> n >> m;
    int from, to, weight;

    adj.resize(n + 1);

    for(int i = 0; i < m; i++){
        fin >> from >> to >> weight;
        Edge edge;
        edge.from = from;
        edge.to = to;
        edge.weight = weight;
        adj[from].push_back(edge);
        edge.to = from;
        edge.from = to;
        adj[to].push_back(edge);
    }

    vector<Edge> mst;
    mst = prim();

    fout << sum << endl << enr << endl;

    for(int i = 0; i < mst.size(); i++){
        fout << mst[i].from << " " << mst[i].to << endl;
    }

    return 0;
}