#include <bits/stdc++.h>

using namespace std;

int randomInt(){
    static std::random_device rd;
    static std::mt19937 mt(rd());
    static uniform_int_distribution<int> distribution(1, 10);

    return distribution(mt);
}

class UnionFind{
private:
    vector<int> father;

public:

    UnionFind(int n){
        father.resize(n);
    }

    void makeSet(int i){
        father[i] = i;
    }

    int findRoot(int x){
        if (x == father.at(x))
            return x;
        else
            return father[x] = findRoot(father.at(x));
    }

    void combine(int x, int y){


        x = findRoot(x);
        y = findRoot(y);

        if (x != y){
            if (randomInt() & 1){
                int t = x;
                x = y;
                y = t;
            }

            father.at(x) = y;
        }
    }
};

class Edge{
public:

    int x, y, w;

    Edge(){}

    Edge(int a, int b, int c){
        x = a;
        y = b;
        w = c;
    }

    friend istream&operator >> (istream& stream, Edge& edge){
        stream >> edge.x;
        stream >> edge.y;
        stream >> edge.w;
        return stream;
    }

    friend ostream&operator << (ostream& stream, const Edge& edge){
        stream << edge.x << " " << edge.y;
        return stream;
    }

    bool operator < (const Edge& E) const{
        return w < E.w;
    }
};

int main() {
//    ifstream cin("data.txt");
    ifstream cin("apm.in");
    ofstream cout("apm.out");

    ios_base::sync_with_stdio(false);

    int N, M;
    cin >> N >> M;

    vector<Edge> edges;
    edges.resize(M);

    for (auto &e: edges)
        cin >> e;

    sort(edges.begin(), edges.end());
    UnionFind unionFind(N);

    for (int i = 0; i < N; i++)
        unionFind.makeSet(i);

    vector<Edge> answerEdges;
    int answer = 0;

    for (int i = 0; i < M; i++){
        int x = edges.at(i).x - 1;
        int y = edges.at(i).y - 1;

        if (unionFind.findRoot(x) != unionFind.findRoot(y)){
            unionFind.combine(x, y);
            answer += edges.at(i).w;
            answerEdges.push_back(edges[i]);
        }
    }

    cout << answer << "\n";
    cout << N - 1 << "\n";

    for (auto e: answerEdges)
        cout << e << "\n";

    return 0;
}