题目：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 \le i \le m$，$1 \le u_i, v_i \le n$）。颜色 $c_i$ 为红色（'r'）、绿色（'g'）或蓝色（'b'）。保证每种颜色的边至少有一条。

对于一条行走（walk）（顶点和边均可重复），记 $s_r, s_g, s_b$ 分别表示行走经过的红色、绿色、蓝色边的重量之和。如果一条边被多次经过，则每次经过都单独计入对应颜色的总重量。

求所有从顶点 $1$ 到顶点 $n$ 的行走中，

$$\max(s_r, s_g, s_b) - \min(s_r, s_g, s_b)$$

的最小值。

---

输入格式

每个测试点包含多个测试用例。第一行输入测试用例个数 $t$（$1 \le t \le 10^4$）。每个测试用例描述如下：

• 第一行三个整数 $n, m, x$（$4 \le n \le 2 \cdot 10^5$，$n-1 \le m \le 2 \cdot 10^5$，$1 \le x \le 2 \cdot 10^5$）—— 顶点数、边数、以及边重量的上界。
• 接下来 $m$ 行，每行包含两个整数 $u_i, v_i$，一个整数 $w_i$ 和一个字母 $c_i$（$1 \le u_i, v_i \le n$，$1 \le w_i \le x$），表示一条连接 $u_i$ 和 $v_i$ 的双向边，重量为 $w_i$，颜色为 $c_i$（'r', 'g', 'b'）。

保证图连通，且每种颜色的边至少有一条。图中可能包含重边和自环。

此外，所有测试用例的 $n$ 的总和、$m$ 的总和、$x$ 的总和各自不超过 $2 \cdot 10^5$。

---

输出格式

对于每个测试用例，输出一个整数 —— 所有从 $1$ 到 $n$ 的行走中，$\max(s_r, s_g, s_b) - \min(s_r, s_g, s_b)$ 的最小值。

---

示例

输入

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$，所以答案是 $3 - 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$。