#include<fstream>
#include<vector>
#include<algorithm>
#include<iostream>
#define NMAX 200005

//in-out
std::ifstream f("apm.in");
std::ofstream g("apm.out");

//data
class Edge{
public:
    int from, to, cost;

    Edge(int from, int to, int cost): from(from), to(to), cost(cost) {}

    bool operator < (const Edge& other){
        return this->cost < other.cost;
    }
};
std::vector<Edge> graph;
std::vector<int> father(NMAX);
std::vector<int> ans;
int n, m, costSol;

int find_(int x){
    if(x == father[x]){
        return x;
    }
    father[x] = find_(father[x]);
    return father[x];
}

void unite_(int x, int y){
    father[find_(x)] = find_(y);
}

void sortEdges(){
    sort(graph.begin(), graph.end());
}

//readData
void readData(){
    f >> n >> m;
    int x, y, c;
    for(int i = 0; i<m; i++){
        f >> x >> y >> c;
        graph.push_back({x, y, c});
    }
}

//solve
void solve(){
    for(int i = 1; i<=n; i++){
        father[i] = i;
    }
    sortEdges();
    int cnt = 0;
    for(const auto& edg : graph){
        if(ans.size() == n - 1){
            return;
        }
        if(find_(edg.from) != find_(edg.to)){
            ans.push_back(cnt);
            unite_(edg.from, edg.to);
            costSol += edg.cost;
        }
        cnt ++;
    }
}

//print solution
void printSolution(){
    g << costSol << '\n';
    g << n - 1 << '\n';
    for(const auto& elem : ans){
        g << graph[elem].from << ' ' << graph[elem].to << '\n';
    }
}

int main(){
    readData();
    solve();
    printSolution();
    return 0;
}