#include <fstream>
#include <vector>
#include <queue>
using namespace std;
// Algoritmul lui Prim
ifstream in("apm.in");
ofstream out("apm.out");

const int maxn = 200001;

struct edge {
    edge(int v, int c) { this->v = v; this->c = c; }
    int v, c;
};

struct comp {
    bool operator() (const edge &a, const edge &b)
    { return b.c < a.c; }
};
priority_queue<edge, vector<edge>, comp> qu[maxn];

int main()
{
    int x, y, c, ct = 0, N, M;
    in >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        in >> x >> y >> c;
        qu[x].push(edge(y, c));
    }
    in.seekg(in.beg);
    in >> N >> M;
    for (int i = 1; i <= M; i++)
    {
        in >> x >> y >> c;
        if ( y != qu[x].top().v && c < qu[y].top().c ) qu[y].push(edge(x, c));
        else if (qu[y].empty()) qu[y].push(edge(x, 0));
    }
    for (int i = 1; i <= N; i++) ct += qu[i].top().c;
    out << ct << '\n';
    out << N-1 << '\n';
    for (int i = 1; i <= N; i++)
        if (qu[i].top().c != 0)
            out << i << ' ' << qu[i].top().v << '\n';
    return 0;
}