#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int N = 2e5 + 1, M = 4e5 + 1;
int n, m, totalCost, edges;
vector <int> tree(N);

struct edge
{
    int x, y, c;
} e[M], afisare[M];

inline void load()
{
    int i;

    in >> n >> m;
    tree.resize(n + 1);

    for(i = 1; i <= n; ++ i)
        tree[i] = i;

    for(i = 1; i <= m; ++ i)
        in >> e[i].x >> e[i].y >> e[i].c;
}

inline void unite(int a, int b)
{
    a = tree[a];
    b = tree[b];

    for(int i = 1; i <= n; ++ i)
        if(tree[i] == b)
            tree[i] = a;
}

bool cmp(edge a, edge b)
{
    return a.c < b.c;
}

void check()
{
    out << "x y c\n";
    for(int i = 1; i <= m; ++ i)
        out << e[i].x << ' ' << e[i].y << ' ' << e[i].c << '\n';
}

void kruskal()
{
    sort(e + 1, e + m + 1, cmp);

   // check();

    for(int i = 1; i <= m; ++ i)
    {
        if(tree[e[i].x] == tree[e[i].y])
            continue;

        unite(e[i].x, e[i].y);
        afisare[++ edges] = e[i];
        totalCost += e[i].c;
    }
}

inline void output()
{
    out << totalCost << '\n' << edges << '\n';
    for(int i = 1; i <= edges; ++ i)
        out << afisare[i].x << ' ' << afisare[i].y << '\n';
}

int main()
{
    load();

    kruskal();

    output();

    return 0;
}