#include <fstream>
#include <queue>
#include <vector>
using namespace std;

struct Edge {
    int cost;
    int id1, id2;
};

struct Node {
    vector<Edge> edges;
};
struct Compare {
    bool operator()(const Edge &e1, const Edge &e2) {
        return e1.cost>e2.cost;
    }
};

priority_queue<Edge, vector<Edge>, Compare> pq;
vector<Edge> treeEdges;
bool luat[200001];
ifstream cin("apm.in");
ofstream cout("apm.out");

int n, m, sum;
Node nodes[200001];

void addEdge(Edge e) {
    sum+=e.cost;
    if(e.id1>=1)treeEdges.push_back(e);
    Node &node=nodes[e.id2];
    luat[e.id2]=true;
    if(node.edges.size()==0)return;
    Edge minEdge={1001, 0, 0};
    for(Edge e:node.edges) {
        if(!luat[e.id2]) {
            pq.push(e);
        }
    }
}

void findNewEdge() {
    while(!pq.empty()) {
        Edge e = pq.top(); pq.pop();
        if(!luat[e.id2]) { // only add edge leading to unvisited node
            addEdge(e);
            break;
        }
    }
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int x, y, c;
        cin>>x>>y>>c;
        nodes[x].edges.push_back({c, x, y});
        nodes[y].edges.push_back({c, y, x});
    }
    addEdge({0,0,1});
    for(int i=2;i<=n;i++) {
        findNewEdge();
    }
    cout<<sum<<'\n'<<treeEdges.size()<<'\n'; 
    for(auto e:treeEdges) {
        sum+=e.cost;
        cout<<e.id1<<' '<<e.id2<<'\n';
    }
    return 0;
}