Contestant SD0062, Xiao Q, in order to steal the SDOI7012 test questions, used advanced hacking techniques to infiltrate the central control system of the SDOI problem-setting team's intranet. However, in addition to the central control system, this intranet also assigns a special communication password to each one-way network cable. The passwords are strings, and different cables may have different passwords. This made things a bit tricky for Xiao Q, but it did not stump him; he quickly analyzed the entire structure of the intranet.

The intranet has $n$ nodes (labeled from $1$ to $n$) and $m$ one-way network cables. The central control system is at node $1$. Each cable connects two nodes in the intranet in one direction, and it is always possible to reach any other node from node $1$ by traversing some number of cables. Each node can run any application. An application carries a communication password, and it can traverse a cable to reach the node at the other end if and only if the application's password matches the cable's password. Traversing each cable takes a certain amount of time.

An application can change its communication password at any node. The time taken to change the password is negligible, but to minimize the amount of change, it must first call a subroutine to calculate the longest common prefix (LCP) of the current password and the cable's password (let its length be $len$). Since retrieving a character of the cable's password is time-consuming, calling this subroutine once costs $len$ units of time.

Additionally, Xiao Q discovered a dictionary in the central control system. The password for each cable is a string from this dictionary. Specifically, this dictionary is a rooted tree with $k$ nodes (labeled from $1$ to $k$), where the root is node $1$. Each edge has a character, and a string $S$ is in the dictionary if and only if there exists a node $u$ such that the sequence of characters on the path from the root to $u$ concatenates to form $S$.

Now, Xiao Q has started $n-1$ applications at node $1$ simultaneously. These applications run in parallel and do not interfere with each other. Each application's initial communication password is empty. He wants to send these applications to all other nodes in the shortest possible time. You need to help Xiao Q calculate the minimum time required for the application to complete its task for each node $i$ ($i = 2, 3, \dots, n$).

Input

The first line is a positive integer $T$, representing the number of test cases.

For each test case:

The first line contains three integers $n, m, k$, representing the number of nodes in the intranet, the number of network cables, and the number of nodes in the dictionary tree, respectively.

The next $m$ lines each contain four integers $a_i, b_i, c_i, d_i$ ($1 \le a_i, b_i \le n, 0 \le c_i \le 20000, 1 \le d_i \le k$), representing that one can travel from node $a_i$ to node $b_i$ in $c_i$ units of time along this cable. The cable's password is the string formed by concatenating the characters on the path from the root of the dictionary tree to node $d_i$ (which may be empty). Note that the intranet may contain self-loops and multiple edges.

The next $k-1$ lines each contain three integers $u_i, v_i, w_i$ ($1 \le u_i, v_i \le k, 1 \le w_i \le 20000$), representing an edge $u_i \to v_i$ in the dictionary tree with character $w_i$ on the edge. It is guaranteed that the given edges form a rooted tree with $1$ as the root, and the characters on the edges outgoing from each node are distinct.

Output

For each test case, output $n-1$ lines, where the $i$-th line represents the minimum time for the application to reach node $i+1$ and complete its task.

Examples

Input 1

1
4 4 6
1 2 2 5
2 3 2 5
2 4 1 6
4 2 1 6
1 2 1
2 3 1
3 4 1
4 5 2
1 6 2

Output 1

2
7
3

Notes

For the example, one feasible path from $1$ to $3$ is $1 \to 2 \to 3$, and the time required is $(2 + lcp(“”, “1112”)) + (2 + lcp(“1112”, “1112”)) = 8$. However, this path is not optimal; the optimal path is $1 \to 2 \to 4 \to 2 \to 3$.

Structure of the intranet in the example

For 100% of the data, $T \le 10$, $2 \le n \le 50000$, $1 \le m \le 50000$, $1 \le k \le 20000$. It is guaranteed that there are at most 2 test cases where $n > 5000$ or $m > 5000$.