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

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

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

};

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];
bool rez[NMAX];
priority_queue<Edge> candidate;
vector<Edge>sol;
int tree_cost = 0, 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].pb({y, c});
        G[y].pb({x, c});
    }
}

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

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

    }
}

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