#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

struct edge { int x,y,cost; };

int n,m;
vector<edge>edges;
vector<int>sol;

class DisjointSet {
    
private:
    
    vector<int> parent;
    
    // compress
    void compress(int node,const int& root) {
        while(node != root) {
            int aux = parent[node];
            parent[node] = root;
            node = aux;
        }
    }
    
public:
    
    DisjointSet(const int& size) {
        parent.resize(size + 1,-1);
    }
    
    // this function returns the root of the node.
    int _find( const int& node ) {
        
        int root = node;
        
        while(parent[root] > 0)
            root = parent[root];
        
        compress(node,root);
        
        return root;
    }
    
    // union by rank
    void _union(int X,int Y) {
        if(parent[X] >= parent[Y]) {
            parent[X] += parent[Y];
            parent[Y] = X;
        }else {
            parent[Y] += parent[X];
            parent[X] = Y;
        }
    }
};

void kruskal() {
    
    DisjointSet disjoint(n);
    
    // sort edges based on their weights.
    sort(edges.begin(),edges.end(),[](const edge& a,const edge& b) {
        return a.cost < b.cost;
    });
    
    int cnt{}, cost{};
    
    for(int i = 0;i < m;++i) {
        
        int rootX = disjoint._find(edges[i].x);
        int rootY = disjoint._find(edges[i].y);
        
        // there is not a cycle
        if(rootX != rootY) {
            cnt++;
            disjoint._union(rootX,rootY);
            sol.push_back(i);
            cost += edges[i].cost;
        }
        
        if(cnt == n - 1)
            break;
    }
    
    g << cost << '\n' << n - 1 << '\n';
    
    for(int it : sol)
        g << edges[it].x << ' ' << edges[it].y << '\n';
}

int main() {
    
    f >> n >> m;
    
    edges.resize(m);
    
    for(int i = 0;i < m;++i)
        f >> edges[i].x >> edges[i].y >> edges[i].cost;
    
    kruskal();
    
    return 0;
}