#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <stack>
#include <tuple>
#include <queue>
#include <list>

using namespace std;

class Graph {
    struct nodeStruct {
        int node1, node2, cost;
        bool operator()(nodeStruct const& n1, nodeStruct const& n2) { return n1.cost > n2.cost; }
    };
    vector<list<nodeStruct>> adjacent;
    vector<list<nodeStruct>> transposed() {
        vector<list<nodeStruct>> ret(adjacent.size());
        for(int i = 0; i < adjacent.size(); i++)
            for(nodeStruct node: adjacent[i])
                ret[node.node2].push_back(nodeStruct({i, node.cost}));
        return ret;
    }
    void dfs(int current, vector<bool> &visited, stack<int> &order) {
        visited[current] = true;
        for(auto i: adjacent[current])
            if(!visited[i.node2])
                dfs(i.node2, visited, order);
        order.push(current);
    }
    void bfs(int current, vector<int> &costs, vector<bool> &visited, deque<int> &queue) {
        queue.push_back(current);
        visited[current] = true;
        costs[current] = 0;
        while(queue.empty() != 1) {
            int k = queue.front();
            for(auto i: adjacent[k])
                if(!visited[i.node2]) {
                    costs[i.node2] += (costs[k] + 1);
                    visited[i.node2] = true;
                    queue.push_back(i.node2);
                }
            queue.pop_front();
        }
    }
    void _biconnected(int node, int parent, vector<bool> &visited, vector<int> &level, vector<int> &minLevel, stack<int> &s, vector<vector<int>> &components, vector<pair<int,int>> &criticalEdges) {
        visited[node] = true;
        minLevel[node] = level[node] = level[parent] + 1;
        s.push(node);
        for (auto x: adjacent[node])
            if (x.node2 != parent) {
                if (visited[x.node2])
                    minLevel[node] = min(minLevel[node], level[x.node2]);
                else {
                    _biconnected(x.node2, node, visited, level, minLevel, s, components, criticalEdges);
                    minLevel[node] = min(minLevel[node], minLevel[x.node2]);
                    if(level[node] < minLevel[x.node2])
                        criticalEdges.emplace_back(node, x.node2);
                    if (minLevel[x.node2] >= level[node]) {
                        components.resize(components.size()+1);
                        while (s.top() != x.node2) {
                            components[components.size()-1].push_back(s.top());
                            s.pop();
                        }
                        components[components.size()-1].push_back(x.node2);
                        s.pop();
                        components[components.size()-1].push_back(node);
                    }
                }
            }
    }
    void _hardConnected(int node, vector<bool> &visited, vector<vector<int>> &components, vector<list<nodeStruct>> &t) {
        visited[node] = false;
        components[components.size() - 1].push_back(node);
        for(auto j: t[node])
            if(visited[j.node2])
                _hardConnected(j.node2, visited, components, t);
    }
    int findParent(int node, vector<int> &parent) {
        if(node == parent[node])
            return node;
        return findParent(parent[node], parent);
    }
public:
    Graph(vector<tuple<int, int, int>> &data, int nrNodes, bool oriented=true) {
        adjacent.resize(nrNodes);
        for(auto[node1, node2, cost]: data) {
            adjacent[node1].push_back(nodeStruct({node1, node2, cost}));
            if(!oriented)
                adjacent[node2].push_back(nodeStruct({node2, node1, cost}));
        }
    }
    friend ostream& operator<< (ostream& os, Graph graph) {
        os << graph.adjacent.size() << " nodes\n";
        for(int i = 0; i < graph.adjacent.size(); i++) {
            os << "node " << i + 1 << ": ";
            for(nodeStruct j: graph.adjacent[i])
                os << "(" << j.node2 + 1 << ", " << j.cost << ") ";
            os << "\n";
        }
        return os;
    }
    int connected() {
        vector<bool> visited(adjacent.size());
        int nr = 0;
        for(int i = 0; i < adjacent.size(); i++)
            if(!visited[i]) {
                stack<int> _;
                nr++;
                dfs(i, visited, _);
            }
        return nr;
    }
    pair<vector<int>, vector<bool>> costs(int start) {
        vector<int> costs(adjacent.size());
        vector<bool> visited(adjacent.size());
        deque<int> queue;
        bfs(start, costs, visited, queue);
        return make_pair(costs, visited);
    }
    stack<int> topologicalSort() {
        vector<bool> visited(adjacent.size());
        stack<int> order;
        for(int i = 0; i < adjacent.size(); i++)
            if(!visited[i])
                dfs(i, visited, order);
        return order;
    }
    pair<vector<vector<int>>, vector<pair<int,int>>> biconnected(){
        stack<int> s;
        vector<int> level(adjacent.size()), minLevel(adjacent.size());
        vector<bool> visited(adjacent.size());
        vector<vector<int>> components;
        vector<pair<int,int>> criticalEdges;
        for (int i = 0; i < adjacent.size(); i++)
            if (visited[i] == 0)
                _biconnected(i, 0, visited, level, minLevel, s, components, criticalEdges);
        return make_pair(components, criticalEdges);
    }
    vector<vector<int>> hardConnected() {
        stack<int> s;
        vector<bool> visited(adjacent.size());
        vector<vector<int>> components;
        vector<list<nodeStruct>> t = transposed();
        for(int i = 0; i < adjacent.size(); i++)
            if(!visited[i])
                dfs(i, visited, s);
        while(!s.empty()){
            if(visited[s.top()]){
                components.resize(components.size() + 1);
                _hardConnected(s.top(), visited, components, t);
            }
            s.pop();
        }
        return components;
    }
    vector<int> dijkstra(int start) {
        vector<int> visited(adjacent.size()), distance(adjacent.size(), -1);
        priority_queue<nodeStruct, vector<nodeStruct>, nodeStruct> costs;
        vector<pair<int, int>> apm;
        costs.push({start, 0});
        distance[start] = 0;
        int cost = 0;
        while(costs.empty() != 1) {
            int node = costs.top().node2;
            costs.pop();
            if(!visited[node])
                for(auto i: adjacent[node]){
                    if(!visited[i.node2])
                        if(distance[i.node2] == -1 || distance[i.node2] > i.cost + distance[node]){
                            distance[i.node2] = i.cost + distance[node];
                            costs.push({i.node2, distance[i.node2]});
                        }
                }
            visited[node] = 1;
        }
        return distance;
    }
    pair<vector<int>, bool> bellmanFord(int start) {
        const int inf = 250001;
        vector<int> visited(adjacent.size()), distance(adjacent.size(), inf);
        priority_queue<nodeStruct, vector<nodeStruct>, nodeStruct> costs;
        costs.push({start, 0});
        distance[start] = 0;
        while(costs.empty() != 1) {
            int node = costs.top().node2;
            costs.pop();
            for(auto i: adjacent[node]){
                if(distance[i.node2] == inf || distance[i.node2] > i.cost + distance[node]){
                    distance[i.node2] = i.cost + distance[node];
                    costs.push({i.node2, distance[i.node2]});
                    visited[node]++;
                    if(visited[i.node2] >= adjacent.size())
                        return make_pair(distance, 1);
                }
            }
            visited[node]++;
        }
        return make_pair(distance, 0);
    }
    pair<vector<nodeStruct>, int> minimumTreeKruskall() {
        priority_queue<nodeStruct, vector<nodeStruct>, nodeStruct> sortedEdges;
        vector<int> parents(adjacent.size());
        vector<nodeStruct> mst;
        int cost = 0;
        for(int i = 0; i < parents.size(); i++)
            parents[i] = i;
        for(int i = 0; i < adjacent.size(); i++)
            for(auto j: adjacent[i])
                sortedEdges.push(j);
        while(!sortedEdges.empty()) {
            nodeStruct node = sortedEdges.top();
            int parent1 = findParent(node.node1, parents);
            int parent2 = findParent(node.node2, parents);
            if(parent1 != parent2) {
                cost += node.cost;
                mst.push_back(node);
                parents[parent1] = parents[parent2];
            }
            sortedEdges.pop();
        }
        return make_pair(mst, cost);
    }
};

int main() {
    ifstream in("apm.in");
    ofstream out("apm.out");
    vector<tuple<int, int, int>> data;
    int n, m, start;
    in >> n >> m; // >> start;
    for(int i = 0; i < m; i++) {
        int aux1, aux2, cost;
        in >> aux1 >> aux2 >> cost;
        data.emplace_back(aux1 - 1, aux2 - 1, cost);
//        data.emplace_back(aux2 - 1, aux1 - 1, cost);
    }
    Graph g(data, n);
    auto graph = g.minimumTreeKruskall();
    out << graph.second << "\n" << graph.first.size() << "\n";
    for(int i = 0; i < graph.first.size(); i++)
        out << graph.first[i].node1 + 1 << " " << graph.first[i].node2 + 1 << "\n";
    return 0;
}