You are given a connected graph with (n) vertices and (m) bidirectional edges with weight not exceeding (x). The (i)-th edge connects vertices (u_i) and (v_i), has weight (w_i), and is assigned a color (c_i) ((1 \leq i \leq m), (1 \leq u_i, v_i \leq n)). The color (c_i) is either red, green, or blue. It is guaranteed that there is at least one edge of each color. For a walk where vertices and edges may be repeated, let (s_r, s_g, s_b) denote the sum of the weights of the red, green, and blue edges that the walk passes through, respectively. If an edge is traversed multiple times, each traversal is counted separately. Find the minimum value of (\max(s_r, s_g, s_b) - \min(s_r, s_g, s_b)) over all possible walks from vertex (1) to vertex (n). Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains three integers (n), (m), and (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)) — the number of vertices, the number of edges in the graph, and the upper bound on the weight of the edges, respectively. The next (m) lines each contain three integers (u_i, v_i, w_i) and a letter (c_i) ((1 \leq u_i, v_i \leq n), (1 \leq w_i \leq x)), representing a bidirectional edge between vertices (u_i) and (v_i) with weight (w_i) and color (c_i). The color (c_i) is either 'r', 'g', or 'b', denoting red, green, and blue, respectively. It is guaranteed that the graph is connected and contains at least one edge of each color. The graph may also contain multiple edges and self-loops . Additionally, it is guaranteed that the total sum of all values of (n), the total sum of all values of (m), and the total sum of all values of (x) across all test cases do not