#include <iostream>
#include <fstream>

using namespace std;

int H[200002];
int Father[200002];


#include <vector>
#include <algorithm>
#include <utility>

ifstream fin("apm.in");
ofstream fout("apm.out");

void Union(int x, int y) {
    if (H[x] > H[y]) Father[y] = x;
    else Father[x] = y;
    if (H[x] == H[y]) H[y]++;
}

int Find_Root(int Node) {
    int Root = Node;
    while (Father[Root]) Root = Father[Root];
    int y = Root, Temp;
    while (y != Root) {
        Temp = Father[y];
        Father[y] = Root;
        y = Temp;
    }
    return Root;
}

struct Edge {
    int X;
    int Y;
    int Cost;
    bool operator< (const Edge& A) {
        return Cost < A.Cost ? 1 : 0;
    }

    Edge(int Ics, int Igrec, int cost) :
        X(Ics),
        Y(Igrec),
        Cost(cost) {}
};
int main()
{
    int N, M;
    vector <Edge> V;
    vector <pair <int, int> > Sol;
    int i, j, x, y, c, Cost = 0;
    fin >> N >> M;
    for (; M; --M) {
        fin >> x >> y >> c;
        V.push_back(Edge(x, y, c));
    }
    sort(V.begin(), V.end());
    for (i = 0, j = 0; i < V.size() && j < N - 1; ++i) {
        x = V[i].X;
        y = V[i].Y;
        c = V[i].Cost;
        int Root1 = Find_Root(x), Root2 = Find_Root(y);
        if (Root1 != Root2) {
            j++;
            Cost += c;
            Union(Root1, Root2);
            Sol.push_back(make_pair(x, y));
        }
    }
    fout << Cost << '\n' << j << '\n';
    for (i = 0; i < N - 1; ++i) {
        fout << Sol[i].first << " " << Sol[i].second << '\n';
    }
    return 0;
}