#include <fstream>
#include <algorithm>

#define Nmax 200100
#define Mmax 400100

using namespace std;

class Forest {

    private:
        int Father[Nmax];

    public:

        void init(int N) {

            for(int i = 1; i <= N; i++)
                Father[i] = i;

        }

        int root(int Node) {

            if(Node != Father[Node])
                Father[Node] = root(Father[Node]);

            return Father[Node];

        }

        bool same(int A, int B) {

            return (root(A) == root(B));

        }

        void unite(int A, int B) {

            Father[A] = B;

        }

};

Forest F;
struct edge {int A, B, Cost;} Edge[Mmax];
int N, M, totalCost, Solution[Nmax];

bool compare(edge X, edge Y) {

    return X.Cost < Y.Cost;

}
void Solve() {

    int i, index, X, Y;

    sort(Edge + 1, Edge + M + 1, compare);

    F.init(N);

    for(i = 1, index = 0; i <= M; i++) {

        X = F.root(Edge[i].A);
        Y = F.root(Edge[i].B);

        if(X != Y) {

            totalCost += Edge[i].Cost;
            Solution[++index] = i;
            F.unite(X, Y);

            }

    }

}
void Read() {

    ifstream in("apm.in");
    in >> N >> M;

    for(int i = 1; i <= M; i++)
        in >> Edge[i].A >> Edge[i].B >> Edge[i].Cost;

    in.close();

}
void Write() {

    ofstream out("apm.out");

    out << totalCost << '\n' << (N - 1) << '\n';

    for(int i = 1; i < N; i++)
        out << Edge[Solution[i]].A << ' ' << Edge[Solution[i]].B << '\n';

    out.close();

}
int main() {

    Read();
    Solve();
    Write();

    return 0;

}