#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define NMAX 220000

using namespace std;

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

priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >, greater<pair<int, pair<int, int> > > >pq;

int n, m;
vector<pair<int, int> > a[NMAX];

int vis[NMAX], leftOp[NMAX], rightOp[NMAX];

int main() {

    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, cost;
        f >> x >> y >> cost;
        x --;
        y --;
        pair<int, int> currentElem(y, cost);
        a[x].push_back(currentElem);
        pair<int, int> currentElem2(x, cost);
        a[y].push_back(currentElem2);
    }


    for (int i = 0; i < a[0].size(); ++i) {
        pair<int, int> pCurent = a[0][i];
        pair<int, int> p1(0, pCurent.first);
        pair<int, pair<int, int> > p2(pCurent.second, p1 );
        pq.push(p2);
    }
    vis[0] = 1;

    int costTotal = 0;

    for (int i = 0; i < n - 1; ++i) {

        pair<int, pair<int, int> > p1 = pq.top();
        pq.pop();
        while (vis[p1.second.second] == 1) {
            p1 = pq.top();
            pq.pop();
        }
        int currentElement = p1.second.second;
        vis[currentElement] = 1;

        costTotal = costTotal + p1.first;
        leftOp[i] = p1.second.first;
        rightOp[i] = p1.second.second;

        //cout << i << " " << currentElement << "\n" << "Vecinii sunt:\n";

        for (int j = 0; j < a[currentElement].size(); ++j) {
            //cout << i << " " << j << "\n";

            pair<int, int> pCurent = a[currentElement][j];
            pair<int, int> p11(currentElement, pCurent.first);
            pair<int, pair<int, int> > p21(pCurent.second, p11 );
            pq.push(p21);


        }
    }

    g << costTotal << "\n";
    g << n - 1 << "\n";
    for (int i = 0; i < n - 1; ++i) {
        g << leftOp[i] + 1 << " " << rightOp[i] + 1 << "\n";
    }


    return 0;
}