#include <fstream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

void dfs (unsigned int node);

const int maxn = 400000;

int N, M;
int VER[maxn], NR;
int sol1, sol2, nod2;
vector <int> VECT[maxn], VECT1[maxn];
vector < pair < int, pair <int, int > > > VECTMU;
vector <pair<int,int> > sol;
int i, x, y, c, cost, nod1;

int main()
{
    ifstream fin ("apm.in");
    fin >> N >> M;
    for (i=1; i<=M; i++)
    {
        fin >> x >> y >> c;
        VECT[x].push_back(y);
        VECT[y].push_back(x);
        VECTMU.push_back(make_pair(c,make_pair(x,y)));
    }
    sort(VECTMU.begin(),VECTMU.end());
    NR = N;
    for (i=0; i<M; i++)
    {
        cost = VECTMU[i].first;
        nod1 = VECTMU[i].second.first;
        nod2 = VECTMU[i].second.second;
        memset(VER,0,sizeof(VER));
        dfs(nod1);
        if (!VER[nod2])
        {
            NR--;
            VECT1[nod1].push_back(nod2);
            VECT1[nod2].push_back(nod1);
            sol1 += cost;
            sol.push_back(make_pair(nod2,nod1));
        }
        if (NR == 1)
            break;
    }
    sol2 = N-1;
    ofstream fout ("apm.out");
    fout << sol1 << '\n';
    fout << sol2 << '\n';
    for (i=0; i<sol2; i++)
        fout << sol[i].first << ' ' << sol[i].second << '\n';
    fout.close();
    return 0;
}

void dfs (unsigned int node)
{
    unsigned int i;
    if (VER[node])
        return;
    VER[node] = 1;
    for (i=0; i<VECT1[node].size(); i++)
        dfs(VECT1[node][i]);
}