#include <algorithm>
#include <fstream>
#include <vector>
using namespace std;

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

const int MAXN = 200010, INF = 1354897345;

int N, M, poz[MAXN], H[MAXN], NH, pred[MAXN];
long long d[MAXN];
bool used[MAXN];
vector < pair <int, long long> > G[MAXN], sol;

inline void sterge(int);
inline void schimba(int, int);
inline void adauga(int);
inline void urca(int);
inline void coboara(int);

void read()
{
    int x, y, cost;

    fin >> N >> M;
    for (int i = 0; i < M; ++i)
    {
        fin >> x >> y >> cost;
        G[x].push_back(make_pair(y, cost));
        G[y].push_back(make_pair(x, cost));
    }
}

void initializeaza()
{
    for (int i = 2; i <= N; ++i)
        d[i] = INF;
}

void restore_road()
{
    int L = sol.size();
    fout << L - 1 << "\n";
    for (int i = 1; i < L; ++i)
        fout << sol[i].first << " " << sol[i].second << "\n";
}

void solve()
{
    adauga(1);
    initializeaza();
    long long scor = 0;
    used[1] = true;

    while ( NH )
    {
        int nod_cr = H[1];
        sterge(1);
        sol.push_back(make_pair(pred[nod_cr], nod_cr));
        scor += d[nod_cr];

        int L = G[nod_cr].size();
        for (int i = 0; i < L; ++i)
        {
            int fiu = G[nod_cr][i].first, cost = G[nod_cr][i].second;
            if ( cost < d[fiu] )
            {
                pred[fiu] = nod_cr;
                d[fiu] = cost;
                if ( !used[fiu] )
                {
                    used[fiu] = true;
                    adauga(fiu);
                }
                else
                    urca(poz[fiu]);
            }
        }
    }

    fout << scor << "\n";
    restore_road();
}

inline void adauga(int nod)
{
    H[++NH] = nod;
    poz[nod] = NH;
    urca(NH);
}

inline void urca(int p)
{
    if ( p == 1 || d[H[p/2]] <= d[H[p]])
        return;

    schimba(p, p/2);
    urca(p/2);
}

inline void schimba(int p1, int p2)
{
    swap(H[p1], H[p2]);
    poz[H[p1]] = p1;
    poz[H[p2]] = p2;
}

inline void sterge(int p)
{
    schimba(p, NH--);
    coboara(p);
}

inline void coboara(int p)
{
    int fiu_st = 2*p, fiu_dr = 2*p + 1, bun = p;

    if ( fiu_st <= NH && d[H[fiu_st]] < d[bun] )
        bun = fiu_st;
    if ( fiu_dr <= NH && d[H[fiu_dr]] < d[bun] )
        bun = fiu_dr;
    if ( bun != p )
    {
        schimba(bun, p);
        coboara(bun);
    }
}

int main ()
{
    read();
    solve();

    fin.close();
    fout.close();

    return 0;
}