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

using namespace std;

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

class graph{
    vector< vector < int > > Ad;
    const int nodes;
    int edges = 0;

    struct disjoint_set{
        int parent, sz;
    };
    struct edge{
        int x, y, c;

        bool operator < ( const edge & E ) {
            return c < E.c;
        }
    };

    int Find( vector < disjoint_set > & ds, int x);
    void Union(vector < disjoint_set > & ds, int x, int y);

public:
    graph( int n):nodes(n){ Ad.resize(nodes+1); }
    graph( int n, int m, vector < vector < int > > & ad ) : nodes(n), edges(m){
        Ad.resize(nodes+1);
        for( int i = 1; i <= edges; ++i ){
            for( int j = 0; j < ad[i].size(); ++i)
                Ad[i].push_back(ad[i][j]);
        }
    }

    void addEdge(int x, int y, bool oriented);
    void DFS( int nod, bool vis[] );
    void BFS( int nod );
    int ConnectedComponents();
    void Kruskal();
};

void graph::addEdge(int x, int y, bool oriented){
    Ad[x].push_back( y );
    if( oriented == false )
        Ad[y].push_back(x);
    edges++;
}
void graph::DFS( int nod, bool vis[] ){
    vis[nod] = 1;
    for( int i = 0; i < Ad[nod].size(); ++i ){
        int w = Ad[nod][i];
        if( vis[w] == 0 )DFS(w,vis);
    }
}
void graph::BFS( int nod ){

    queue < int > Q;

    int dist[nodes] = {0};
    Q.push(nod);
    int x;

    while( !Q.empty() ){
        x = Q.front();
        Q.pop();

        for( int i = 0; i < Ad[x].size(); ++i ){
            int w = Ad[x][i];

            if( dist[w] == 0 && w != x && w != nod ){
                dist[w] = dist[x] + 1;
                Q.push(w);
            }
        }
    }

    for( int i = 1; i <= nodes; ++i )
        if( dist[i] != 0 || i == nod )fout << dist[i] << ' ';
        else fout << "-1 ";
}
int graph::ConnectedComponents(){
    int nr = 0;
    bool vis[nodes] = {0};
    for( int i = 1; i <= nodes; ++i )
        if( vis[i] == 0 ){
            DFS(i,vis);
            nr++;
        }
    return nr;
}
int graph::Find( vector < disjoint_set > & ds, int x){

    int aux, root = x;
    while( ds[root].parent != root ) root = ds[root].parent;
    while( ds[x].parent != x ){
        aux = ds[x].parent;
        ds[x].parent = root;
        x = aux;
    }
    return root;
}
void graph::Union(vector < disjoint_set > & ds, int x, int y){

    int root_x = Find(ds,x);
    int root_y = Find(ds,y);

    if( ds[root_x].sz >= ds[root_y].sz ){
        ds[root_x].sz += ds[root_y].sz;
        ds[root_y].parent = root_x;
    }
    else{
        ds[root_y].sz += ds[root_x].sz;
        ds[root_x].parent = root_y;
    }
}
void graph::Kruskal(){
    vector < disjoint_set > disjoint_sets;
    vector < edge > E;

    int M;
    fin >> M;
    int x, y, c;

    disjoint_sets.resize(nodes+1);
    for( int i = 1; i <= nodes; ++i )
        disjoint_sets[i] = {i,1};

    for( int i = 1; i <= M; ++i ){
        fin >> x >> y >> c;
        E.push_back({x,y,c});
    }

    sort( E.begin(), E.end() );

    vector < pair < int , int > > Sol;
    int C = 0, edges_nr = 0;

    for( int i = 0; i < M && edges_nr < nodes; ++i ){
        int root_x = Find(disjoint_sets, E[i].x);
        int root_y = Find(disjoint_sets, E[i].y);
        if( root_x != root_y ){
            edges_nr++;
            Sol.push_back( {E[i].x, E[i].y} );
            C += E[i].c;
            Union(disjoint_sets, root_x, root_y );
        }
    }
    fout << C << '\n';

    fout << Sol.size() << '\n';
    for( int i = 0; i < Sol.size(); ++i )
        fout << Sol[i].first << ' ' << Sol[i].second << '\n';
}

int main()
{
    int N;
    fin >> N;
    graph G(N);
    G.Kruskal();

    return 0;
}