#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <limits.h>

using namespace std;

struct edge{
    int weight, node;
};

class myComparator{
    public:
        int operator() (const edge& e1, const edge& e2){
            return e1.weight > e2.weight;
        }
};

//number of nodes and edges
int n, m;
//min heap ordering edges by weight
priority_queue <edge, vector<edge>, myComparator> q;
//adjacency lists
vector<list<pair<int, int>>> L;
//MCST
list<pair<int, int>> MCST;
//MCST info
int cost, numberOfEdges;
//
bool * isInMCST;
int * parent, * minCostToConnect;

void readEdges(ifstream & in){
    int u, v, w;
    while(in>>u>>v>>w){
        L[u].push_back(make_pair(v,w));
        L[v].push_back(make_pair(u,w));
    }
}

void prim(){
    edge e;
    isInMCST[1] = true;

    for(auto p : L[1]){
        //if the node has not been added to the MCST and it has a lower cost to connect from the current node
        if(!isInMCST[p.first] && (p.second < minCostToConnect[p.first])){
            //update minimum cost to connect
            minCostToConnect[p.first] = p.second;
            //update parent
            parent[p.first] = 1;
            //add the edge to queue
            q.push(edge{p.second, p.first});
        }
    }

    while(!q.empty()){
        e = q.top();
        q.pop();
        if(isInMCST[e.node])
            continue;
        //add node to the MCST
        isInMCST[e.node] = true;
        cost += e.weight;
        numberOfEdges++;
        MCST.push_back(make_pair(e.node, parent[e.node]));
        //traverse the neighbours
        for(auto p : L[e.node]){
            //if the node has not been added to the MCST and it has a lower cost to connect from the current node
            if(!isInMCST[p.first] && (p.second < minCostToConnect[p.first])){
                //update minimum cost to connect
                minCostToConnect[p.first] = p.second;
                //update parent
                parent[p.first] = e.node;
                //add the edge to queue
                q.push(edge{p.second, p.first});
            }
        }
    }
}

int main(){
    ifstream in("grafpond.in");
    ofstream out("grafpond.out");
    in>>n>>m;
    L.resize(n + 1);
    readEdges(in);

    isInMCST = new bool[n + 1];
    parent = new int[n + 1];
    minCostToConnect = new int[n + 1];
    for(int i = 1; i <= n; i++){
        isInMCST[i] = false;
        parent[i] = 0;
        minCostToConnect[i] = INT_MAX; 
    }

    prim();

    out<<cost<<endl<<numberOfEdges<<endl;
    for(auto p : MCST){
        out<<p.first<<' '<<p.second<<endl;
    }
}