#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("a.in");
ofstream g("a.out");
vector <pair <int,int > > M[200001];
vector < int > MF[200001];
priority_queue < pair <int,int> > C;
long long int noduri,muchi,nod1,nod2,cost,CostTotal;
bool Vizitat[200001];
void parcurgere(int nod_cur)
{
    cout<<nod_cur<<" ";
    if (Vizitat[nod_cur]) return;
    Vizitat[nod_cur]=true;
    int nod_urmator;
    for (int i=0;i<M[nod_cur].size();++i)
    {
        if (Vizitat[M[nod_cur][i].first]==false)
        {
            C.push(M[nod_cur][i]);
        }
    }
    nod_urmator = C.top().first;
    while (Vizitat[nod_urmator]==true&&C.size())
    {
        C.pop();
        nod_urmator = C.top().first;
    }
    if (C.size())
    {
    CostTotal += C.top().second;
    C.pop();
    MF[nod_cur].push_back(nod_urmator);
    parcurgere(nod_urmator);
    }
}
int main()
{
    f>>noduri>>muchi;
    for (int i=0;i<muchi;++i)
    {
        f>>nod1>>nod2>>cost;
        M[nod1].push_back( make_pair(nod2,cost) );
        M[nod2].push_back( make_pair(nod1,cost) );
    }
    parcurgere(1);
    g<<CostTotal<<'\n'<<noduri-1<<'\n';

    for (int i=1;i<=noduri;++i)
    {
        for (int j=0;j<MF[i].size();++j)
        {
            g<<i<<" "<<MF[i][j]<<'\n';
        }
    }
}