#include <fstream>
#include <algorithm>

using namespace std;

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

struct edgesVector {
    int cost, x, y;
};

const int NMAX = 2e5 + 5, MMAX = 4e5 + 5;
edgesVector Edges[MMAX];
int N, M, Father[NMAX], APM[NMAX - 1];

int getFather(int x)
{
    if(Father[x] == 0)
        return x;
    Father[x] = getFather(Father[x]);
    return Father[x];
}

inline bool checkOrder(edgesVector A, edgesVector B)
{
    return A.cost < B.cost;
}

int main()
{
    in >> N >> M;
    for(int i = 1; i <= M; i++)
        in >> Edges[i].x >> Edges[i].y >> Edges[i].cost;
    sort(Edges + 1, Edges + M + 1, checkOrder);
    int cost = 0, RootX, RootY, index = 0;
    for(int i = 1; i <= M; i++)
    {
        RootX = getFather(Edges[i].x);
        RootY = getFather(Edges[i].y);
        if(RootX == RootY)
            continue;
        cost += Edges[i].cost;
        Father[RootY] = RootX;
        APM[++index] = i;
    }
    out << cost << '\n' << N-1 << '\n';
    for(int i = 1; i <= index; i++)
        out << Edges[APM[i]].x << ' ' << Edges[APM[i]].y << '\n';
    return 0;
}