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

using namespace std;

ifstream fin("apm.in");

const int NMAX = 200005;

vector < pair < int, int > > G[NMAX];
priority_queue < pair < int, pair < int, int > > > pq;
vector < pair < int, int > > edges;
int dad[NMAX];
bool viz[NMAX];

int N, M, total_cost, nodes;

void read(){
    fin >> N >> M;
    for(int i = 0; i < M; ++i){
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }
}

void prim(){
    pq.push({0, {1, - 1}});
    while(!pq.empty() && nodes <= N){
        auto cap = pq.top();
        pq.pop();

        int cost = -cap.first;
        int nod = cap.second.first;

        if(viz[nod]){
            continue;
        }

        nodes++;
        viz[nod] = true;
        total_cost += cost;
        edges.push_back(cap.second);

        for(auto nbr: G[nod]){
            if(!viz[nbr.first]){
                pq.push({-nbr.second, {nbr.first, nod}});
            }
        }
    }
}

void print(){
    fout << total_cost << "\n";
    fout << N - 1 << "\n";
    for(auto edge: edges){
        if(edge.second == -1){
            continue;
        }
        fout << edge.first << " " << edge.second << "\n";
    }
}

int main()
{
    read();
    prim();
    print();
    return 0;
}