#include <iostream>
#include <fstream>
#include <vector>
#include <utility>
#include <set>
#define mx 200000
using namespace std;

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

struct muchie{int a,b,cost;};
struct comp {
  bool operator() (const muchie& lhs, const muchie& rhs)
  {return lhs.cost<rhs.cost;}
};

int N, n, m, NrMuchii, CostTotal, sol[mx];

vector< pair<int, int> > Adiacenta[mx]; // first nod || second cost
set< muchie , comp > MuchiiCurente; // first nod || second cost
void Read(), Write(), Solve();

void AdaugaMuchii(int nod)
{
    for(int i=0;i<Adiacenta[nod].size();++i)
        if(!sol[Adiacenta[nod][i].first])
            {
                muchie m;
                m.a=nod;
                m.b=Adiacenta[nod][i].first;
                m.cost=Adiacenta[nod][i].second;
                MuchiiCurente.insert(m);
            }
}




void Solve()
{
    int nod;
    AdaugaMuchii(1);
    N--;

    for(;N;)
    {
        sol[(*MuchiiCurente.begin()).a]=(*MuchiiCurente.begin()).b;
        CostTotal+=(*MuchiiCurente.begin()).cost;
        MuchiiCurente.erase(*MuchiiCurente.begin());
        NrMuchii++;
        N--;
        AdaugaMuchii((*MuchiiCurente.begin()).b);
    }

}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}

void Write()
{
    g<<CostTotal<<'\n'<<NrMuchii<<'\n';
    for(int i=1;i<=NrMuchii;++i)
        g<<i<<' '<<sol[i]<<'\n';
   // g<<'\n';
}

void Read()
{
    f>>n>>m;
    N=n;
    int nod1, nod2, cost;
    for(;m--;)
    {
        f>>nod1>>nod2>>cost;
        Adiacenta[nod1].push_back(make_pair(nod2, cost));
        Adiacenta[nod2].push_back(make_pair(nod1, cost));
    }
}