Дан взвешенный неориентированный граф на \(n\) вершинах, а также \(q\) троек \((u, v, l)\), в каждой из которых \(u\) и \(v\) — некоторые вершины графа, а \(l\) — натуральное число. Назовём ребро \(e\) полезным, если существует хотя бы одна тройка \((u, v, l)\), для которой найдётся путь (не обязательно простой) в графе со следующими свойствами:
- \(u\) и \(v\) являются концами этого пути,
- путь содержит ребро \(e\),
- сумма весов рёбер этого пути не превосходит \(l\).
Найдите количество полезных рёбер в этом графе.
Выходные данные
Выведите одно число — количество полезных рёбер в графе.
Примечание
В первом примере каждое ребро полезно, кроме ребра веса \(5\).
Во втором примере полезно только ребро между \(1\) и \(2\), потому что оно принадлежит пути \(1-2\), и \(10 \leq 11\). С другой стороны, ребро между вершинами \(3\) и \(4\) не является полезным.
В третьем примере оба ребра полезны, например, потому что существует путь \(1-2-3-2\) длины \(5\). Обратите внимание, что путь может проходить через вершины по нескольку раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
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
|
3 2
1 2 1
2 3 2
1
1 2 5
|
2
|