#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

const int INF = 1e9;
const int MAXN = 200000;

vector<pair<int,int>> G[MAXN + 5];

int n, m;
long long cost_total=0;

int D[MAXN+5];
int T[MAXN+5];
bool sel[MAXN+5];

void Prim(int start) {
    for (int i=1;i<=n;i++) {
        D[i]=INF;
        T[i]=0;
        sel[i]=false;
    }

    D[start]=0;

    for (int i=1;i<=n;i++){
        int u=0;
        int best=INF;

        for (int v=1;v<=n;v++) {
            if (D[v]<best && !sel[v]) {
                best=D[v];
                u=v;
            }
        }

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

        for (auto &edge : G[u]) {
            int v=edge.first;
            int c=edge.second;

            if (c<D[v] && !sel[v]) {
                D[v]=c;
                T[v]=u;
            }
        }
    }
}

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

    for (int i=1;i<=m;i++) {
        int a, b, c;
        f>>a>>b>>c;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }

    Prim(1);

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

    return 0;
}