#include <fstream>
#include <vector>
#include <queue>
#define pb push_back
#define NMAX 200005
#define MMAX 400005
using namespace std;

ifstream f("apm.in");
ofstream g("apm.out");

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

class Edge{
public:

    int x, y, cost;
    Edge(int x, int y, int cost):x{x}, y{y}, cost{cost}{}
    bool operator < (const Edge& ot)const {
        return this->cost > ot.cost;
    }
};


vector<Node> G[NMAX];
bool rez[NMAX];
priority_queue<Edge>candidate;
vector<Edge> sol;
int tree_cost = 0, n, m;

void read_data(int &n, int &m){
    f >> n >> m;
    for(int i = 1; i<=m; i++){
        int x, y, c;
        f >> x >> y >> c;
        G[x].pb({y, c});
        G[y].pb({x, c});
    }
}

void init(int start){
    rez[start] = true;
    for(const auto& node : G[start]){
        candidate.push({start, node.y, node.cost});
    }
}

void solve(){
    while(!candidate.empty()){
        auto edge = candidate.top();
        candidate.pop();
        if(!(rez[edge.x] && rez[edge.y])){
            sol.pb(edge);
            tree_cost += edge.cost;
            int new_node;
            if(!rez[edge.x]) {
                new_node = edge.x;
            }
            else{
                new_node = edge.y;
            }
            init(new_node);
        }
    }
}

int main(){
    read_data(n, m);
    init(1);
    solve();
    g << tree_cost << '\n' << sol.size() << '\n';
    for(const auto& edg : sol){
        g << edg.x << ' ' << edg.y << '\n';
    }
}