#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

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


const int INF = 1e9;


int n, m, nr;
long long cost_total = 0;

vector<vector<int>> COST;


vector<int> D;
vector<int> T;
vector<bool> sel;

void Prim(int start_node) {
    D.assign(n + 1, INF);
    T.assign(n + 1, 0);
    sel.assign(n+1, false);

    D[start_node]=0;

    for (int count=1; count<=n; count++) {
        int u_min=0;
        int min_cost=INF;

        for (int v=1;v<=n;v++) {
            if (D[v]<min_cost && sel[v]==false) {
                min_cost=D[v];
                u_min=v;
            }
        }

        sel[u_min] = true;
        cost_total += D[u_min];

        for (int v=1;v<=n;v++) {
            int cost_uv=COST[u_min][v];

            if (cost_uv<D[v] && sel[v]==false) {
                D[v]=cost_uv;
                T[v]=u_min;
            }
        }
    }
}

int main() {
    f>>n>>m;

    COST.assign(n+1, vector<int>(n+1, INF));
    for (int i=1;i<=n;i++) {
        COST[i][i] = 0;
    }

    for (int i=1;i<=m;i++) {
        int nod1, nod2, c;
        f>>nod1>>nod2>>c;
        COST[nod1][nod2] = min(COST[nod1][nod2], c);
        COST[nod2][nod1] = min(COST[nod2][nod1], c);
    }

    Prim(1);

    g<<cost_total<<'\n';
    g<<n-1<<'\n';
    for (int i=1;i<=n;i++) {
        if (T[i]!=0){
            g<<T[i]<<" "<<i<<'\n';
        }
    }

    return 0;
}