#include <bits/stdc++.h>

using namespace std;

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

const int NMAX=2e5+5;

int N, M, i, X, Y, C, nod, T[NMAX], j;

int cost=0;

int Sel[NMAX];

vector <pair <int, int> > G[NMAX];

priority_queue <pair<int, pair<int, int> >, vector <pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > >  > H;

int main()
{
    f>>N>>M;

    for(i=1; i<=N; i++)
        T[i]=i;

    for(i=1; i<=M; i++)
    {
        f>>X>>Y>>C;

        G[X].push_back({Y, C});
        G[Y].push_back({X, C});
    }

    Sel[1]=true;

    for(i=0; i<G[1].size(); i++)
        H.push({G[1][i].second, {1, G[1][i].first}});

    for(i=1; i<N; i++)
    {
        while(Sel[H.top().second.second]==1)
            H.pop();

        nod=H.top().second.second;

        Sel[nod]=true;

        T[nod]=H.top().second.first;

        cost+=H.top().first;

        for(j=0; j<G[nod].size(); j++)
            if(!Sel[G[nod][j].first])
                H.push({G[nod][j].second, {nod, G[nod][j].first}});
    }

    g<<cost<<'\n';

    g<<N-1<<'\n';

    T[1]=0;

    for(i=2; i<=N; i++)
        g<<T[i]<<' '<<i<<'\n';

    return 0;
}