F. Полезные рёбра
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан взвешенный неориентированный граф на $$$n$$$ вершинах, а также $$$q$$$ троек $$$(u, v, l)$$$, в каждой из которых $$$u$$$ и $$$v$$$ — некоторые вершины графа, а $$$l$$$ — натуральное число. Назовём ребро $$$e$$$ полезным, если существует хотя бы одна тройка $$$(u, v, l)$$$, для которой найдётся путь (не обязательно простой) в графе со следующими свойствами:

  • $$$u$$$ и $$$v$$$ являются концами этого пути,
  • путь содержит ребро $$$e$$$,
  • сумма весов рёбер этого пути не превосходит $$$l$$$.

Найдите количество полезных рёбер в этом графе.

Входные данные

В первой строке даны два целых числа $$$n$$$ и $$$m$$$ ($$$2\leq n\leq 600$$$, $$$0\leq m\leq \frac{n(n-1)}2$$$).

Каждая из следующих $$$m$$$ строк содержит три числа $$$u$$$, $$$v$$$ и $$$w$$$ ($$$1\leq u, v\leq n$$$, $$$u\neq v$$$, $$$1\leq w\leq 10^9$$$), обозначающих, что в графе есть ребро между вершинами $$$u$$$ и $$$v$$$ с весом $$$w$$$.

Следующая строка содержит единственное число $$$q$$$ ($$$1\leq q\leq \frac{n(n-1)}2$$$) — количество троек.

Каждая из следующих $$$q$$$ строк содержит по три числа $$$u$$$, $$$v$$$ и $$$l$$$ ($$$1\leq u, v\leq n$$$, $$$u\neq v$$$, $$$1\leq l\leq 10^9$$$), обозначающих тройку $$$(u, v, l)$$$.

Гарантируется, что:

  • граф не содержит петель и кратных рёбер,
  • все пары $$$(u, v)$$$ в тройках попарно различны.
Выходные данные

Выведите одно число — количество полезных рёбер в графе.

Примеры
Входные данные
4 6
1 2 1
2 3 1
3 4 1
1 3 3
2 4 3
1 4 5
1
1 4 4
Выходные данные
5
Входные данные
4 2
1 2 10
3 4 10
6
1 2 11
1 3 11
1 4 11
2 3 11
2 4 11
3 4 9
Выходные данные
1
Входные данные
3 2
1 2 1
2 3 2
1
1 2 5
Выходные данные
2
Примечание

В первом примере каждое ребро полезно, кроме ребра веса $$$5$$$.

Во втором примере полезно только ребро между $$$1$$$ и $$$2$$$, потому что оно принадлежит пути $$$1-2$$$, и $$$10 \leq 11$$$. С другой стороны, ребро между вершинами $$$3$$$ и $$$4$$$ не является полезным.

В третьем примере оба ребра полезны, например, потому что существует путь $$$1-2-3-2$$$ длины $$$5$$$. Обратите внимание, что путь может проходить через вершины по нескольку раз.