#include <bits/stdc++.h>

using namespace std;

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

#define NMAX 200010
#define inf 0x3f3f3f3f

struct NodCost {
    int nod, cost;
    bool operator < (const NodCost &other) const
    {
        return cost > other.cost;
    }
};

int dist[NMAX];
vector<NodCost> G[NMAX];
priority_queue<NodCost> q;
int n, m, cost;
bool in_apm[NMAX];
int dad[NMAX];

void read()
{
    int i, x, y, c;
    fin>>n>>m;
    for(i = 0; i < m; ++i) {
        fin>>x>>y>>c;
        G[x].push_back({y,c});
        G[y].push_back({x,c});
    }
}

void prim() {
    int i;
    for(i = 1; i <= n; ++i) {
        dist[i] = inf;
    }
    in_apm[1] = 1;
    dist[1] = 0;

    for(auto vec: G[1]) {
        dist[vec.nod] = vec.cost;
        q.push(vec);
        dad[vec.nod] = 1;
    }

    while(!q.empty()) {
        auto top = q.top();
        q.pop();
        if(in_apm[top.nod]) continue;

        in_apm[top.nod] = 1;
        cost += top.cost;

        for(auto vec: G[top.nod]) {
            if(!in_apm[vec.nod] && vec.cost < dist[vec.nod]) {
                dist[vec.nod] = vec.cost;
                q.push(vec);
                dad[vec.nod] = top.nod;
            }
        }
    }
}

void afisare() {
    fout<<cost<<'\n';
    fout<<n-1<<'\n';
    for(int i = 2; i <= n; ++i) {
        fout<<i<<' '<<dad[i]<<'\n';
    }
}

int main()
{
    read();
    prim();
    afisare();
    return 0;
}