#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 4e5 + 5;

struct Edge
{
    int x, y, c;
    bool operator < (const Edge other) const
    {
        return this -> c < other.c;
    }
};

Edge M[N];
pair <int, int> sol[N];
int n, m, k, f[N / 2];

void Read ()
{
    ifstream fin ("apm.in");
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> M[i].x >> M[i].y >> M[i].c;
    fin.close();
}

inline void Union (int x, int y)
{
    f[x] = y;
}

int Find (int x)
{
    int root, y;
    root = x;
    while (f[root])
        root = f[root];
    while (x != root)
    {
        y = f[x];
        f[x] = root;
        x = y;
    }
    return root;
}

void APM ()
{
    sort(M + 1, M + m + 1);
    int totalcost = 0;
    for (int i = 1; i <= m; i++)
    {
        int x1 = Find(M[i].x);
        int y1 = Find(M[i].y);
        int c1 = M[i].c;
        if (x1 != y1)
        {
            Union(x1, y1);
            sol[++k] = {M[i].y, M[i].x};
            totalcost += c1;
        }
    }
    ofstream fout ("apm.out");
    fout << totalcost << "\n" << k << "\n";
    for (int i = 1; i <= k; i++)
        fout << sol[i].first << " " << sol[i].second << "\n";
    fout.close();
}

int main()
{
    Read();
    APM();
    return 0;
}