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

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

struct muchie{int a,b,cost, d;};
struct comp {
  bool operator() (const muchie& a, const muchie& b)
  {return (a.cost!=b.cost) ? a.cost<b.cost:a.d<b.d ;}
};

int N, n, m, NrMuchii, CostTotal, k;
bool nods[mx];//memorez ce am parcurs
deque<muchie> sol;
vector< pair<int, int> > Adiacenta[mx]; // first nod || second cost
set< muchie , comp > MuchiiCurente;
void Read(), Write(), Solve(), AdaugaMuchii(int), Eliminare(int,int);



void Eliminare(int a, int b)
{
    for(int i=0;i<Adiacenta[a].size();i++)
        if(Adiacenta[a][i].first==b) Adiacenta[a][i].first=0;
    for(int i=0;i<Adiacenta[b].size();i++)
        if(Adiacenta[b][i].first==a) Adiacenta[b][i].first=0;
}

void AdaugaMuchii(int nod)
{
    for(int i=0;i<Adiacenta[nod].size();++i)
    {

        if((Adiacenta[nod][i].first!=0)&&(!nods[Adiacenta[nod][i].first]))
            {
                muchie m;
                m.a=nod;
                m.b=Adiacenta[nod][i].first;
                m.cost=Adiacenta[nod][i].second;
                m.d=k++;
                MuchiiCurente.insert(m);
            }
    }
}

void Solve()// Prim (cred)
 {
    int A,B,C;
    AdaugaMuchii(1);
    nods[1]=1;
    N--;
    for(;N;)
    {
        for(;nods[(*MuchiiCurente.begin()).b];)
            MuchiiCurente.erase(*MuchiiCurente.begin());

        A=(*MuchiiCurente.begin()).a;
        B=(*MuchiiCurente.begin()).b;
        C=(*MuchiiCurente.begin()).cost;

        sol.push_front(*MuchiiCurente.begin());
        nods[B]=1;
        CostTotal+=C;
        NrMuchii++;
        N--;
        Eliminare(A,B);
        MuchiiCurente.erase(*MuchiiCurente.begin());
      /*  if((A==9)&&(B==8))
            {
                set<muchie,comp> aux=MuchiiCurente;
                for(;aux.size();)
                {
                    g<<(*aux.begin()).a<<' '<<(*aux.begin()).b<<'\n';
                    aux.erase(*aux.begin());
                }


            }*/

        AdaugaMuchii(B);
    }

}

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



void Write()
{
    int a,b;
    muchie aux;
    g<<CostTotal<<'\n'<<NrMuchii<<'\n';
    for(int i=1;i<=NrMuchii;++i)
    {
        aux=sol.back();
        sol.pop_back();
        a=aux.a;
        b=aux.b;
        g<<a<<' '<<b<<'\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));
    }
}