#include <iostream>
#include <fstream>
#define Nmax 200003
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("apm.in");
ofstream fout("apm.out");

int t[Nmax];
int h[Nmax];


class pereche
{ public :
    int x,y,cost;
    bool operator < (const pereche & ) const;
};

bool pereche::operator<(const pereche &x) const
{
    return (cost<x.cost);
}

int n,m;
vector <pereche>v;

void Citire ()
{ int i,x,y,z;
    fin>>n>>m;
    for (i=1;i<=m;i++)
    {
        pereche w;
        fin>>x>>y>>z;
        w.x=x;
        w.y=y;
        w.cost=z;
        v.push_back(w);
    }
}

int Find (int x)
{   if (t[x]==0) return x;
    return Find(t[x]);
}
void Union (int x,int y)
{

    int c1=Find(x);
    int c2=Find(y);
    if (h[c1]<h[c2]) t[c1]=c2;
    if (h[c2]<h[c1]) t[c2]=c1;
    else {
        t[c1]=c2;
        h[c2]++;
    }
}


void Kruskal ()
{
    int dim=0;
    int i=0;
    int cost_total=0;
    vector <pereche> sol;
    while (dim!=n-1)
    {

        pereche aux=v[i];
        if (Find (aux.x)!=Find (aux.y))
        {
            sol.push_back(aux);
            dim++;
            cost_total+=aux.cost;

            Union(aux.x,aux.y);

        }
        i++;
    }
    fout<<cost_total<<"\n"<<sol.size()<<"\n";

    for (pereche it:sol)
    {
        fout<<it.x<<" "<<it.y<<"\n";
    }
}

int main()
{
    Citire ();
    sort (v.begin(),v.end());
    Kruskal();
    return 0;
}