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

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

struct edge{
    int from, to, cost;
    friend bool operator < (const edge& a, const edge& b){
        if(a.cost > b.cost)
            return true;
        return false;
    }

    edge();
    edge(int _from, int _to, int _cost){
        from = _from; to = _to, cost = _cost;
    }
};

vector<pair<int,int>> graph[200505];
priority_queue<edge>pq;
queue<edge>apm;
int N, M, x, y, c, minCost;
bool visited[200505];

int main()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++){
        fin >> x >> y >> c;
        graph[x].push_back(make_pair(y, c));
        graph[y].push_back(make_pair(x, c));
    }

    for(auto x: graph[1]){
        edge aux(1, x.first, x.second);
        pq.push(aux);
    }
    visited[1] = true;

    int neededEdges = N - 1;
    int curentEdges = 0;

    while(!pq.empty() && neededEdges != curentEdges){
        int thisNode = pq.top().to, cost = pq.top().cost;

        if(visited[thisNode]){
            pq.pop();
            continue;
        }

        visited[thisNode] = true;
        minCost += cost;

        curentEdges++;
        apm.push(pq.top()); pq.pop();

        for(auto x: graph[thisNode]){
            if(!visited[x.first]){
                edge aux(thisNode, x.first, x.second);
                pq.push(aux);
            }
        }
    }

    fout << minCost << endl << neededEdges << endl;
    while(!apm.empty()){
        fout << apm.front().from << ' ' << apm.front().to << endl;
        apm.pop();;
    }

    return 0;
}