题目描述

SD0062 号选手小 Q 同学为了偷到 SDOI7012 的试题，利用高超的黑客技术潜入了 SDOI 出题组的内联网的中央控制系统，然而这个内联网除了配备有中央控制系统，还为内联网中的每条单向网线设定了特殊的通信口令，这里通信口令是一个字符串，不同网线的口令可能不同。这让小 Q 同学感觉有些棘手， 不过这根本难不倒他，很快他就分析出了整个内联网的结构。

内联网中有 $n$ 个节点（从 $1$ 到 $n$ 标号）和 $m$ 条单向网线，中央控制系统在第 $1$ 个节点上，每条网线单向连接内联网中的某两个节点，从 $1$ 号节点出发经过若干条网线总能到达其他任意一个节点。每个节点都可以运行任意的应用程序，应用程序会携带一条通信口令，当且仅当程序的口令与网线的口令相同时，程序才能通过这条网线到达另一端的节点继续运行，并且通过每条网线都需要花费一定的时间。

每个应用程序可以在任意一个节点修改通信口令，修改通信口令花费的时间可以忽略不计，但是为了减小修改量，需要先调用一个子程序来计算当前程序的口令和网线的口令的最长公共前缀（记其长度为 $\text{len}$），由于获取网线的口令的某个字符会比较耗时，调用一次这个子程序需要花费 $\text{len}$ 个单位时间。

除此之外，小 Q 同学还在中央控制系统中发现了一个字典，每条网线的口令都是字典中的某个字符串。具体来说，这个字典是一棵 $k$ 个节点（从 $1$ 到 $k$ 标号）的有根树，其中根是第 $1$ 个节点，每条边上有一个字符，字符串 $S$ 在字典中当且仅当存在某个点 $u$ 使得从根节点出发往下走到 $u$ 的这条路径上的字符顺次拼接构成 $S$。

现在小 Q 同学在 $1$ 号节点同时开启了 $n − 1$ 个应用程序，这些应用程序同时运行且互不干扰，每个程序的通信口令都为空，他希望用最短的时间把这些程序分别发送到其他节点上，你需要帮小 Q 同学分别计算出发送到第 $i(= 2, 3, \dots, n)$ 个节点的程序完成任务的最短时间。

输入格式

第一行是一个正整数 $T$，表示测试数据的组数，

对于每组测试数据，

第一行是三个整数 $n$，$m$，$k$，分别表示内联网的节点数、内联网的网线条数、字典树的节点数，

接下来 $m$ 行，每行包含四个整数 $a_i$，$b_i$，$c_i$, $d_i$（$1 \leq a_i, b_i \leq n$，$0 \leq c_i \leq 20000$，$1 \leq d_i \leq k$），表示沿着这条网线可以从第 $a_i$ 个节点花费 $c_i$ 个单位时间到达第 $b_i$ 个节点，网线的口令是由从字典树的根到 $d_i$ 这个点的路径上的字符顺次拼接构成的字符串（可能为空），需要注意的是这个内联网可能有自环和重边，

接下来 $k − 1$ 行，每行包含三个整数 $u_i$，$v_i$，$w_i$（$1 \leq u_i, v_i \leq k$，$1 \leq w_i \leq 20000$），表示字典树上有一条 $u_i \rightarrow v_i$ 的边，边上有字符 $w_i$，保证给出的边构成一棵以 $1$ 为根的有根树，并且每个点连出去的边上的 字符互不相同。

输出格式

对于每组测试数据，输出 $n − 1$ 行，第 $i$ 行表示发送到第 $i + 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

2
7
3

数据范围与提示

对于 $100\%$ 的数据，$T \leq 10$，$2 \leq n \leq 50000$，$1 \leq m \leq 50000$，$1 \leq k \leq 20000$，保证满足 $n > 5000$ 或 $m > 5000$ 的数据不超过 $2$ 组。