#include <bits/stdc++.h>
#define N 200005

using namespace std;

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

typedef pair <int, int> pereche;
int n, m, costTot, costMin[N], T[N];
bool viz[N];
vector <pereche> L[N];
priority_queue < pereche, vector<pereche>, greater<pereche> > Q;
/// (cost, nod)

void Prim(int root)
{
    for (int i = 1; i <= n; i++)
    {
        costMin[i] = INT_MAX;
        T[i] = 0;
    }
    Q.push(make_pair(0, root));
    costMin[root] = 0;

    while (!Q.empty())
    {
        int nod = Q.top().second;
        viz[nod] = 1;

        Q.pop();

        for (auto urm : L[nod])
        {
            int nextNod = urm.second;
            int cost = urm.first;

            if (!viz[nextNod] && cost < costMin[nextNod])
            {
                costMin[nextNod] = cost;
                T[nextNod] = nod;
                Q.push(make_pair(cost, nextNod));
            }
        }
    }

}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b, c;
        fin >> a >> b >> c;

        L[a].push_back(make_pair(c, b));
        L[b].push_back(make_pair(c, a));
    }

    Prim(1);

    for (int i = 1; i <= n; i++)
        costTot += costMin[i];

    fout << costTot << "\n";
    for (int i = 2; i <= n; i++)
        fout << T[i] << " " << i << "\n";
    return 0;
}