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

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

struct Node{
    int y, cost;
    Node(int y, int cost): y{y}, cost{cost} {}
};

struct Edge{
    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];
priority_queue<Edge>candidate;
vector<Edge>sol;
bool solved[NMAX];
int cost_sol;
int n, m;

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

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

void prim(){
    while(!candidate.empty()){
        auto edg = candidate.top();
        candidate.pop();
        if(!(solved[edg.x] && solved[edg.y])){
            sol.push_back(edg);
            int next_node;
            if(!solved[edg.x]){
                next_node = edg.x;
            }else{
                next_node = edg.y;
            }
            init(next_node);
        }
    }
}

void print_sol(){
    for(const auto& edg: sol){
        cost_sol += edg.cost;
    }
    g << cost_sol << ' ' << n - 1<< '\n';
    for(const auto& edg: sol){
        g << edg.x << ' ' << edg.y << '\n';
    }
}

int main(){
    read_data();
    init(1);
    prim();
    print_sol();
    return 0;
}