Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×
G. RGB Прогулка
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Red and Blue and Green - fn and Silentroom
⠀

Дан связный граф с $$$n$$$ вершинами и $$$m$$$ двунаправленными рёбрами, вес которых не превышает $$$x$$$. $$$i$$$-е ребро соединяет вершины $$$u_i$$$ и $$$v_i$$$, имеет вес $$$w_i$$$ и имеет цвет $$$c_i$$$ ($$$1 \leq i \leq m$$$, $$$1 \leq u_i, v_i \leq n$$$). Цвет $$$c_i$$$ может быть красным, зеленым или синим. Гарантируется, что есть по крайней мере одно ребро каждого цвета.

Для прогулки, где вершины и рёбра могут повторяться, пусть $$$s_r, s_g, s_b$$$ обозначают сумму весов красных, зеленых и синих рёбер, через которые проходит прогулка, соответственно. Если по ребру проходят несколько раз, каждое прохождение учитывается отдельно.

Найдите минимальное значение $$$\max(s_r, s_g, s_b) - \min(s_r, s_g, s_b)$$$ среди всех возможных прогулок от вершины $$$1$$$ до вершины $$$n$$$.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$x$$$ ($$$4 \leq n \leq 2 \cdot 10^5$$$, $$$n-1 \leq m \leq 2 \cdot 10^5$$$, $$$1 \leq x \leq 2 \cdot 10^5$$$) — количество вершин, количество рёбер в графе и верхнее ограничение на вес рёбер, соответственно.

Следующие $$$m$$$ строк каждая содержат три целых числа $$$u_i, v_i, w_i$$$ и букву $$$c_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$1 \leq w_i \leq x$$$), представляющие двунаправленное ребро между вершинами $$$u_i$$$ и $$$v_i$$$ с весом $$$w_i$$$ и цветом $$$c_i$$$. Цвет $$$c_i$$$ может быть 'r', 'g' или 'b', обозначающий красный, зеленый и синий соответственно.

Гарантируется, что граф связен и содержит по крайней мере одно ребро каждого цвета. Граф также может содержать кратные рёбра и петли.

Кроме того, гарантируется, что сумма $$$n$$$, сумма $$$m$$$ и сумма $$$x$$$ по всем наборам входных данных не превосходят $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальное значение $$$\max(s_r, s_g, s_b) - \min(s_r, s_g, s_b)$$$ среди всех прогулок от вершины $$$1$$$ до вершины $$$n$$$.

Пример
Входные данные
3
4 3 3
1 2 2 r
2 3 3 g
3 4 2 b
4 5 4
1 2 1 r
1 1 1 r
2 1 1 r
2 3 4 g
3 4 4 b
4 6 4
1 2 2 r
1 2 2 r
2 3 3 b
1 3 4 r
1 4 1 g
3 4 4 g
Выходные данные
1
0
0
Примечание

В первом наборе входных данных оптимальный путь: $$$1 \to 2 \to 3 \to 4$$$. Используемые рёбра:

  • $$$1 \to 2$$$ (красное, вес $$$2$$$)
  • $$$2 \to 3$$$ (зеленое, вес $$$3$$$)
  • $$$3 \to 4$$$ (синее, вес $$$2$$$)

Итого $$$s_r = 2$$$, $$$s_g = 3$$$, и $$$s_b = 2$$$. Таким образом, ответ равен $$$1$$$.

Во втором наборе входных данных один из оптимальных путей: $$$1 \to 1 \to 2 \to 1 \to 2 \to 3 \to 4$$$. Используемые рёбра:

  • $$$1 \to 1$$$ (красное, вес $$$1$$$)
  • $$$1 \to 2$$$ (красное, вес $$$1$$$)
  • $$$2 \to 1$$$ (красное, вес $$$1$$$)
  • $$$1 \to 2$$$ (красное, вес $$$1$$$)
  • $$$2 \to 3$$$ (зеленое, вес $$$4$$$)
  • $$$3 \to 4$$$ (синее, вес $$$4$$$)

Итого $$$s_r = s_g = s_b = 4$$$. Таким образом, ответ равен $$$0$$$.