You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

小明最近学习了最短路算法，AC了CSP-J2023第四题，然后就膨胀了。

题目描述 2s 1024MB

本题保证最终时限是std的$1.5$倍以上，空间限制是std的五倍以上，但不保证最后还是按$2s$给时限。

小明有一天做梦，梦见自己来到了松鼠的王国。

松鼠的王国可以看成是一棵$n$个节点的树，根节点是$1$号，所有的树边$u,v,w$都是从父亲向儿子方向连通单向连通的，表示从父亲节点走到儿子节点，需要花$w$颗松子作为过路费。

除此之外，还有$m_1$条松鼠地铁：

第$i$条松鼠地铁可以用五个参数描述：$u,v,a,b,w$，表示从$u$到$v$路径上的任何一个节点，可以花费$w$颗松子乘坐松鼠地铁，到达$a$到$b$路径上的任何一个节点下车。

除此之外，还有$m_2$条额外的松鼠洞，第$i$个松鼠洞可以用三个参数描述：

$u,v,w$，表示从$u$子树（含$u$）内任何一个节点，可以花$w$颗松子掉进第$i$个松鼠洞，然后从$v$子树（含$v$）内任何一个节点钻出来。

小明不得不感叹，自己真会做梦，梦里都能见到OI题。我相信你也知道小明要问什么，题面上就不说小明要求$1$到每个点的最小花费了。

输入格式

第一行输入$n,m_1,m_2$。

接下来$n-1$行，首先输入$u,v,w$，表示这$n-1$条树边。

接下来输入$m_1$行，每行$u,v,a,b,w$。

接下来输入$m_2$行，每行$u,v,w$。

输出格式

输出一行$n$个数字，表示$1$到每一个点的最小花费。

6 1 1
1 2 1
2 3 1
2 4 100
1 5 100
5 6 100
3 2 3 4 10
4 5 1

0 1 2 11 12 12

样例解释 #1

上图是灵魂画手画出来的图。

数据范围

对于100%的数据：$1\leq n\leq 3\times 10^5,0\leq m_1,m_2\leq 10^5,1\leq w\leq 10^9$。其他参数保证合法。