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

#define NMax 2010
#define INF 2000000000

using namespace std;

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

int nodes, edges, tcost, k, father[NMax], d[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;
        d[it->first] = it->second;
    }

    for (int i=2; i<=nodes; i++)
        if (father[i] != 1)
            d[i] = INF;

    while (!H.empty()) {
        while (!H.empty() && mark[H.top().first])
            H.pop();

        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] && d[it->first] > it->second) {
                d[it->first] = it->second;
                father[it->first] = crtNode;
                H.push(make_pair(it->first, it->second));
            }
        }
    }

    g<<tcost<<"\n";
    g<<nodes-1<<"\n";
    for (int i=1; i<=k; i++)
        g<<sol[i].ext1<<" "<<sol[i].ext2<<"\n";
    return 0;
}