#include <fstream>
#include <vector>
#include <queue>

#define NMax 2010

using namespace std;

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

int nodes, edges, tcost, k, father[NMax];
vector< pair<int, int> > G[NMax];
bool mark[NMax];
struct graph {
    int ext1;
    int ext2;
} sol[4010];

class op {
public:
    bool operator() (pair<int, int> d1, pair<int, int> d2)
    {
        return d1.second > d2.second;
    }
};
priority_queue< pair<int, int>, vector< pair<int, int> >, op> H;

int main()
{
    f>>nodes>>edges;
    
    int node1, node2, cost;
    for (int i=1; i<=edges; i++) {
        f>>node1>>node2>>cost;
        
        G[node1].push_back(make_pair(node2, cost));
        G[node2].push_back(make_pair(node1, cost));
    }
    
    mark[1] = true;
    for (vector< pair<int, int> >::iterator it = G[1].begin(); it != G[1].end(); ++it) {
        H.push(make_pair(it->first, it->second));
        father[it->first] = 1;
    }
    
    while (!H.empty()) {
        int crtNode = H.top().first;
        int crtCost = H.top().second;
        H.pop();
        
        tcost += crtCost;
        ++k;
        sol[k].ext1 = crtNode;
        sol[k].ext2 = father[crtNode];
        mark[crtNode] = true;
        
        for (vector< pair<int, int> >::iterator it = G[crtNode].begin(); it != G[crtNode].end(); ++it) {
            if (!mark[it->first]) {
                H.push(make_pair(it->first, it->second));
                father[it->first] = crtNode;
            }
        }
    }
    
    g<<tcost<<"\n";
    g<<nodes-1<<"\n";
    for (int i=1; i<=k; i++)
        g<<sol[i].ext1<<" "<<sol[i].ext2<<"\n";
    return 0;
}