#include <bits/stdc++.h>
using namespace std;

const int INF = 2147483647;

class Graph{
    int Nodes, nrEdges, startNode;
    vector<pair<int, double>> *adjacencyList;

public:
    int getNodes() { return this->Nodes;}

    void readAdjancencyList();
    void Prim();
};

void Graph::readAdjancencyList() {
    ifstream fin("apm.in");
    fin >> this->Nodes;
    fin >> this->nrEdges;

    this->adjacencyList = new vector<pair<int,double>> [this->Nodes + 1];

    int x, y, pondere;
    fin >> x >> y >> pondere;
    this->adjacencyList[x].push_back({y,pondere});
    this->adjacencyList[y].push_back({x,pondere});
    this->startNode = x;

    for(int i = 1; i < this->nrEdges; i++){
        fin >> x >> y >> pondere;
        this->adjacencyList[x].push_back({y,pondere});
        this->adjacencyList[y].push_back({x,pondere});
    }

    fin.close();
}

void Graph::Prim() {
    ofstream fout("apm.out");
    // distances and dad vectors
    vector <int> d, dad;
    vector <bool> visited;
    for(int i = 0; i <= this->Nodes; i++){
        d.push_back(INF);
        dad.push_back(0);
        visited.push_back(false);
    }

    // set the starting node
    d[this->startNode] = 0;

    // declare the priority queue
    priority_queue<pair<double, int>> Q;
    // add the distance * (-1) in the priority queue so it will work
    // like a min heap
    Q.push({(-1) * d[this->startNode], this->startNode});

    while(!Q.empty()){
        int Node = Q.top().second;
        Q.pop();

        visited[Node] = true;
        for(int i = 0; i < this->adjacencyList[Node].size(); i++){
            int NodeNext = this->adjacencyList[Node][i].first;
            int weight = this->adjacencyList[Node][i].second;

            if(!visited[NodeNext] && d[NodeNext] > weight){
                dad[NodeNext] = Node;
                d[NodeNext] = weight;
                Q.push({ (-1) * d[NodeNext], NodeNext});
            }
        }
    }

    double cost = 0;
    for(int i = 1; i < d.size(); i++)
        cost += d[i];

    fout << cost << endl;
    fout << dad.size() - 2 << endl;
    for(int i = 1; i < dad.size(); i++)
        if( i != this->startNode)
            fout << i << " "  << dad[i] << endl;
}

int main() {
    Graph graf;
    graf.readAdjancencyList();
    graf.Prim();
    return 0;
}