#include <fstream>
#include <vector>
#define DIM 200010
#define INF 2000000000

using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

vector< pair<int, int> > L[DIM], S;
int H[DIM], D[DIM], P[DIM];
pair<int, int> T[DIM];


int n, cost, m, i, dH, c, p, x, y, k, inHeap;

void swap(int &a, int &b) {
    int aux = a;
    a = b;
    b = aux;
}

int main () {
    fin>>n>>m;
    for (i=1;i<=m;i++) {
        fin>>x>>y>>c;
        L[x].push_back( make_pair(y, c) );
        L[y].push_back( make_pair(x, c) );
    }

    for (i=2;i<=n;i++)
        D[i] = INF;

    H[1] = 1;
    P[ H[1] ] = 1;
    T[1] = make_pair(0, 0);
    dH = 1;
    D[1] = 0;

    while (1) {
        k = H[1];
        if (T[k].first != 0) {
            S.push_back(make_pair(T[k].first, k));
            cost += T[k].second;
            if (S.size() == n-1)
                break;
        }
        H[1] = H[dH--];
        P[ H[1] ] = 1;
        c = 1;
        p = 2*c;
        while (c <= dH) {
            if (c + 1 <= dH && D[  H[c+1] ] < D[ H[c] ])
                c++;
            if (D[ H[c] ] < D[ H[p] ]) {
                swap(H[c], H[p]);
                P[ H[c] ] = c;
                P[ H[p] ] = p;
                p = c;
                c = 2*p;
            } else
                break;
        }
        for (i=0;i<L[k].size();i++)
            if (D[ L[k][i].first ] > L[k][i].second) {
                if (D[ L[k][i].first ] == INF)
                    inHeap = 0;
                else
                    inHeap = 1;
                D[ L[k][i].first ] = L[k][i].second;

                T[L[k][i].first] = make_pair(k, L[k][i].second);

                if (!inHeap) {
                    dH++;
                    H[dH] = L[k][i].first;
                    P[H[dH]] = dH;
                }
                if (inHeap)
                    c = P[L[k][i].first];
                else
                    c = dH;
                p = c/2;

                while (p) {
                    if (D[ H[c] ] < D[ H[p] ]) {
                        swap(H[c], H[p]);
                        P[ H[c] ] = c;
                        P[ H[p] ] = p;
                        c = p;
                        p = p/2;
                    } else
                        break;
                }

            }

    }
    fout<<cost<<"\n"<<n-1<<"\n";
    for (i=0;i<n-1;i++)
        fout<<S[i].first<<" "<<S[i].second<<"\n";
    return 0;
}