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

#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;
multiset<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.insert(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()) {
        int crtNode = (*H.begin()).first;
        int crtCost = (*H.begin()).second;
        H.erase(H.begin());

        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) {
                for (multiset< pair<int, int> >::iterator ith = H.begin(); ith != H.end(); ith++) {
                    if (ith->first == it->first && ith->second == it->second) {
                        H.erase(ith);
                        break;
                    }
                }

                d[it->first] = it->second;
                father[it->first] = crtNode;
                H.insert(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;
}