诗(poem)

[题目描述]

你想写诗，但你甚至不会写字。

不过你想到了一个假装写诗的方法——复制。

把一首诗看成一个字符串，字符集为 ${0,1,2}$ .

你从网上找来了 $m$ 首诗(可惜这些是付费的),第i首诗为$s_i$,满足$\sum |s_i|\leq L$，其中 $|s_i|$ 表示 $s_i$ 的长度（字符串的下标从0开始)

同时每首诗有两个数值,$和a_{i,0}和a_{i,1}$，表示前缀和后缀的版权费。

三元组 $(i,j,0)$ 表示字符串$s_{i,0},s_{i,1},\cdots,s_{i,j-1}$ ,即 $s_i$长为j的前缀。

三元组$(i,j,1)$ 表示字符串$s_{i,|s_i|-j},s_{i,|s_i|-j+1},\cdots,s_{i,|s_i|-1}$ ,即 $s_i$ 长为j的后缀。

$str1+str2$表示将字符串str1和str2前后拼接起来形成的新字符串。

你的写诗方法可以看成三元组序列:

$(i_1,j_1,k_1),(i_2,j_2,k_2),\cdots,(i_t,j_t,k_t),0\leq k_i\leq1$

你写出的诗就是 $(i_1,j_1,k_1)+(i_2,j_2,k_2)+\cdots+(i_t,j_t,k_t)$ .

你花的版权费就是 $\sum_{1\leq z\leq t} a_{i_z,k_z}$

很快你发现，对于一个给定的诗S，按照上述方法，你可能有多种方法写出它（这时候你会选择版权费花费最小的），亦或没有方法。

给你一棵TRIE树T，以1为根，对于TRIE树上的节点u,$S_u$表示从根到u遍历的边形成的字符串（按照从根到u的顺序）。

对于$S_u$ ,求出写诗方案中最小的版权费，亦或表示没有方案，输出-1。

[输入格式]

输入

第一行三个整数 $n,m,L$ 表示TRIE树节点数，模板诗总数，模板诗长度和限制。

接下来n行，每行三个整数 $s,e,c$,表示TRIE树上一条s->e,字符为c的边,保证每个点出边的字符互不相同。

接下来m行，每行两个整数和一个字符串 $a_{i,0},a_{i,1},s_i$ .

[输出格式]

输出。

n行,第u行一个整数,表示$S_u$最小的版权费，亦或表示没有写作方案，输出-1。

特别的,S_1的版权费一定是0。

[样例]

见选手目录下poem/poem1.in,poem2.in,poem3.in,poem4.in和poem/poem1.out,poem2.out,poem3.out,poem4.out

poem2和poem3有子任务2和3的特殊性质。

[数据范围]

对于100%的数据,$所有字符0\leq a_{i,0},a_{i,1}\leq10^9,L=3*10^5,所有字符\in\{0,1,2\}$

大样例下载