#include <bits/stdc++.h>

using namespace std;

const int NMAX=2e5+5;

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

long long cost=0;

bool 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()
{
    freopen("apm.in", "r", stdin);
    freopen("apm.out", "w", stdout);

    scanf("%d%d", &N, &M);

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

    for(i=1; i<=M; i++)
    {
        scanf("%d%d%d", &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]==true)
            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]==false)
                H.push({G[nod][j].second, {nod, G[nod][j].first}});
    }

    printf("%d\n", cost);

    printf("%d\n", N-1);

    T[1]=0;

    for(i=2; i<=N; i++)
        printf("%d %d\n", T[i], i);

    printf("\n");

    return 0;
}