#include <fstream>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define pb push_back
#define mp make_pair

using namespace std;

const int NMAX = 400005 ;
const int INF = 0x3f3f3f3f ;


struct Edge
{
    int x; int y; int cost ;
} unu;

int N, M, S, SOL[NMAX], cost, noduri[NMAX] ;


vector <Edge> A ;

ifstream fin("apm.in") ;
ofstream fout("apm.out") ;


bool compare(Edge a, Edge b)
{
    if(a.cost < b.cost)
        return true;
    return false ;
}

int search_edge(int edge)
{

    if(edge != noduri[edge])
        noduri[edge] = search_edge(noduri[edge]) ;

    return noduri[edge] ;

}

inline void R(int cord_x, int cord_y)
{
    noduri[search_edge(cord_x)] = search_edge(cord_y) ;
}

inline void Kruskal()
{
    sort(A.begin(), A.end(), compare) ;

    for(int i = 1 ; i <= N ; ++ i)
        noduri[i] = i ;

    for(int i = 0 ; i < M && SOL[0] != N - 1 ; ++ i)
        if(search_edge(A[i].x) != search_edge(A[i].y))
        {
            cost += A[i].cost ;
            SOL[++SOL[0]] = SOL[0] ;
            R(A[i].x, A[i].y) ;

        }
}


int main()
{
    fin >> N >> M ;

    for(int i = 1 ; i <= M ; ++ i)
    {
        fin >> unu.x >> unu.y >> unu.cost ;
        A.push_back(unu) ;
    }

    Kruskal() ;

    fout << cost << '\n' ;
    fout << SOL[0] << '\n' ;

    for(int i = 1 ; i <= SOL[0] ; ++ i)
        fout << A[SOL[i]].y << ' ' << A[SOL[i]].x << '\n' ;

    fin.close() ;
    fout.close() ;
    return 0;
}