#include <fstream>
#include <algorithm>

#define NMax 400010

using namespace std;

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

int n, m, disjoint[NMax], cost;
struct graph {
    int ext1;
    int ext2;
    int cost;
} G[NMax], sol[NMax];

bool cmp(const graph &vert1, const graph &vert2) {
    return vert1.cost < vert2.cost;
}

int findRoot(int node)
{
    while (disjoint[node] > 0)
        node = disjoint[node];
    
    return node;
}

int main()
{
    
    f>>n>>m;
    
    for (int i=1; i<=m; i++)
        f >> G[i].ext1 >> G[i].ext2 >> G[i].cost;
    
    sort (G+1, G+m+1, cmp);
    
    for (int i=1; i<=n; i++)
        disjoint[i] = -1;
    
    int node1, node2, root1, root2, i=1, j=0, l=0;
    while (i <= n-1) {
        l++;
        node1 = G[l].ext1;
        node2 = G[l].ext2;
        
        root1 = findRoot(node1);
        root2 = findRoot(node2);
        
        if (root1 != root2) {
            if ((-disjoint[root1]) > (-disjoint[root2])) {
                disjoint[root2] = root1;
                disjoint[root1] += (-disjoint[root2]);
            }
            else {
                disjoint[root1] = root2;
                disjoint[root2] += (-disjoint[root1]);
            }
            
            cost += G[l].cost;
            sol[++j].ext1 = node1;
            sol[j].ext2 = node2;
            
            i++;
        }
    }
    
    g<<cost<<"\n"<<n-1<<"\n";
    
    for (int i=1; i<=j; i++)
        g<<sol[i].ext1<<" "<<sol[i].ext2<<"\n";
    
    return 0;
}