#include <iostream>
#include <queue>
#include <functional>
#include <fstream>
#define DIM 10000
#define inf 300000

class Node{
public:
    int nr;
    int p;
    int key;
    bool taken;
};

class adj_node{
public:
    int y;
    int cost;
    adj_node(int y, int cost):y{y},cost{cost}{}
};

void read(int &n, int &m, std::vector<adj_node> G[]){
    std::ifstream f("apm.in");
    f>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,cost;
        f>>x>>y>>cost;
        G[x].push_back(adj_node(y,cost));
        G[y].push_back((adj_node(x,cost)));
    }
    f.close();
}

int main() {
    std::vector<adj_node> G[DIM];
    Node node[DIM];
    int n,m;
    read(n,m,G);
    auto cmp=[&](int x, int y){return node[x].key>node[y].key;};
    std::priority_queue<int,std::vector<int>, decltype(cmp)> pq(cmp);
    for(int i=1;i<=n;i++){
        node[i].p = -1;
        node[i].key = inf;
        node[i].nr = i;
        node[i].taken = false;
        pq.push(i);
    }
    node[1].key=0;
    node[1].p=-1;
    node[1].nr=1;
    int sum=0;
    while(!pq.empty()){
        auto nd=pq.top();
        node[nd].taken= true;
        for(auto v:G[nd]){
            if(!(node[v.y].taken)&&(node[v.y].key>v.cost)) {
                if (node[v.y].key == inf) {
                    sum += v.cost;
                } else {
                    sum += v.cost - node[v.y].key;
                }
                node[v.y].key = v.cost;
                node[v.y].p = nd;
            }
        }
        pq.pop();
    }
    std::ofstream g("apm.out");
    g<<sum<<"\n"<<n-1<<"\n";
    for(int i=1;i<=n;i++){
        if(node[i].p!=-1){
            g<<node[i].p<<" "<<i<<"\n";
        }
    }
    g.close();
    return 0;
}