Optimal Communication Scheduling in an Internal Network

You are given an internal network with n nodes (numbered from 1 to n) and m directed cables. The central control system is located at node 1. Each cable has an associated travel time and a communication password – a string that is guaranteed to appear in a given dictionary.

The dictionary is given as a rooted tree with k nodes (numbered 1 to k) with node 1 as the root. Each edge of the dictionary tree carries a character. A string S is in the dictionary if and only if there exists some node such that the path from the root to that node, when reading the characters on the edges in order, forms S (in LaTeX format, one may write it as $S$).

At time zero, node 1 simultaneously launches n-1 application programs (one for each of the nodes 2 through n). Each program runs independently and carries a communication password. Initially, every program carries an empty password. An application program running at a node can only traverse an outgoing cable if its current password is exactly the same as the cable’s password. However, at any node, the program can change its password arbitrarily (the time to change the password is negligible), but before changing (or using) the password to traverse a cable, the program must call a subroutine which computes the longest common prefix (LCP) between its current password and the cable’s password. This subroutine takes a time equal to the length of the LCP. Only then can the program adjust its password to exactly match the cable and traverse it – incurring also the cable’s travel time.

Formally, if an application program at a node is currently carrying password P and it wishes to traverse a cable with password S and travel time w, it must first call the subroutine at a cost of $\mathrm{LCP}(P,S)$ time (where $\mathrm{LCP}(P,S)$ is the length of the longest common prefix between P and S), then update its password to S (for free), and finally spend w time to traverse the cable. The total cost for traversing that cable is thus w + LCP(P,S). Note that the initial password is the empty string, so $\mathrm{LCP}("", S) = 0$ for any cable.

It is guaranteed that starting from node 1, every other node is reachable via a sequence of cables.

Your task is to compute the minimum time required for the program to reach each node i (for i = 2, 3, \dots, n).

Input/Output formats are described below.

inputFormat

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

The next k - 1 lines each contain a parent node and a character: For i = 2 to k, each line contains an integer p and a character c, meaning that there is an edge from node p to node i in the dictionary with label c. The string corresponding to a node in the dictionary is obtained by concatenating the characters on the edges from the root (node 1) to that node.

The next m lines describe the cables. Each line contains two integers u and v, an integer w representing the travel time, and a nonempty string S. This represents a directed cable from node u to node v in the network. It is guaranteed that S is a string in the dictionary.

outputFormat

Output n - 1 lines. The i-th line (for i = 2, 3, \dots, n) should contain a single integer representing the minimum time required for the program to reach node i.

sample

3 3 3
1 a
1 b
1 2 5 a
1 3 10 b
2 3 2 a

5
8