#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std ;


const int NMAX = 200001, MMAX = 400001 ;

class Muchie
{
public:
    int a , b , cost ;
    bool ok ;
    Muchie (int A , int B , int COST)
     {
        a = A ;
        b = B ;
        cost = COST ;
        ok = false;
    };
};

class graf
{
    vector <Muchie> muchii ;
    int n , m , tata[NMAX] , rang[NMAX] ;
    void initializeaza() ;
    int radacina (int) ;
    void uneste (int , int ) ;
    bool sunt_unite(int , int ) ;

public:
    graf () ;
    void kruskal() ;
};


bool comp (Muchie a , Muchie b)
{
    return a.cost < b.cost ;
}

 graf::graf()
{
    ifstream in ("apm.in") ;
    int a , b , c ;
    in>>n>>m ;
    for (int i = 1 ; i <= m ; i++)
    {
        in>>a>>b>>c ;
        muchii.push_back (Muchie(a , b , c)) ;
    }
    in.close() ;
}

void graf::initializeaza()
{
     for (int i = 1 ; i <= n ; i++) rang[i]=tata[i]=i ;
}


int graf::radacina(int x)
{
    if (x == tata[x]) return x ;
    tata[x] = radacina (tata[x]) ;
    return tata[x] ;
}

void graf::uneste(int a , int b)
{
    a = radacina(a) ;
    b = radacina(b) ;
    if (rang[b] > rang[a]) tata[a] = b ;
    else tata[b] = a ;
    if (rang[a] == rang[b]) rang[a]++ ;
}

bool graf::sunt_unite (int a , int b)
{
    a = radacina(a) ;
    b = radacina(b) ;
    return a == b ;
}
void graf::kruskal()
{
    initializeaza() ;
    sort(muchii.begin() , muchii.end() , comp) ;
    int a , b , c ;
    int cost = 0, nr = 0 ;

    for (int i = 0 ; i < m ; i++)
    {
        a = muchii[i].a ;
        b = muchii[i].b ;
        c = muchii[i].cost ;
        if (!sunt_unite(a, b))
        {
            uneste(a, b);
            muchii[i].ok = true;
            cost += c;
            nr++;
        }

    }
    ofstream out ("apm.out") ;
    out<<cost<<"\n"<<nr<<"\n" ;
    for (int i = 0 ; i < m ; i++)
        if (muchii[i].ok) out<<muchii[i].a<<" "<< muchii[i].b<<"\n" ;
    out.close() ;
}

int main()
{
    graf orlando ;
    orlando.kruskal() ;
    return 0 ;
}