NOI2025正在绍兴举办，小丫为闭幕式表演制作了一个机器人并打算操控它从仓库走到礼堂。 绍兴的道路系统可以简化为n个路口以及连接这些路口的m条单行道路，且每条道路有一定的长度。为了方便将道路系统录入机器人的芯片，小丫对每一个路口连接的所有道路进行了编号。具体而言，若有d条道路以路口为起点，则这d条道路会被小Y按照某种顺序编号为 1∼d ， 分别称作以为起点的第 1∼d 条道路。 小丫的机器人内部有一个参数p。给定参数p的上限K与修改费用v1,v2 ,…..,vk−1,w2,w3,…….,wk。小Y将按照如下规则设置与修改机器人的参数: 初始时，小Y将参数p设置为1。 在任意时刻，小丫可以远程控制机器人修改参数:
初始时，小丫的机器人位于机器人仓库，即路口1。当机器人位于路口x时，记以路口为起点的第p条道路的终点为y，道路长度为z，则小Y可以花费z的费用操控机器人从x走到y。特别地，若以路口为起点的道路不足p条，则小Y无法操控机器人走动。 小Y并不知道闭幕式表演所在的礼堂位于哪个路口，因此他需要对每个路口都做好准备。请你帮助他求出将机器人从仓库移动到每个路口所需费用的最小值。
输入的第一行包含一个非负整数c，表示测试点编号。c=0表示该测试点为样例。 输入的第二行包含三个正整数n,m,k,分别表示路口数量、道路数量与参数p的上限。 输入的第三行包含k-1个非负整数v1,…….,vk-1，表示增加参数p的费用。 输入的第四行包含-1个非负整数w2,...,wk，表示减少参数p的费用。 输入的第i+4(1≤i≤n)行包含若干个正整数，其中第一个非负整数山表示以路口i为起点的道路数量，接下来 2di个正整数 yi,1,zi,1,yi2,zi,2,…….,yi,d,zi,di~~，表示以路口i为起点的道路，其中 yi,j,zi,j(1≤j<di)分别表示编号为j的道路的终点与长度。
输出一行n个整数，其中第i(1≤i≤n)个数表示小Y将机器人从仓库移动到路口i所需费用的最小值。特别地，若小Y无法将机器人从仓库移动到该路口，则输出-1.
0 5 6 3 2 4 1 1 3 2 5 3 1 4 2 1 3 2 2 1 2 4 1 0 0
0 5 3 4 -1
【样例1解释】 小Y可以按照以下方案将机器人分别从仓库移动到路口1~4: 对于路口1:小Y的机器人初始时即位于路口1，因此所需费用为0: 对于路口 2:小Y操控机器人沿以路口1为起点的第1条道路走到路口2，所需费用为 5; 对于路口 3:小Y将参数p增加1，然后操控机器人沿以路口1为起点的第2条道路走到路口3，所需费用为2+1=3; 对于路口4:小Y将参数p增加1，然后操控机器人沿以路口1为起点的第2条道路走到路口3，再操控机器人沿以路口3为起点的第2条道路走到路口4，所需费用为2+1+1=4。 可以证明，上述移动方案的所需费用均为最小值。 对于路口 5:由于小Y无法将机器人移动到路口5，因此输出 -1。
【样例 2】 见选手目录下的 robot/robot2.in与robot/robot2.ans。 该样例满足测试点3~5的约束条件。
【样例 3】 见选手目录下的robot/robot3.in与robot/robot3.ans. 该样例满足测试点6~8的约束条件。
【样例 4】 见选手目录下的robot/robot4.in与robot/robot4.ans该样例满足测试点9,10的约束条件。
【样例 5】 见选手目录下的robot/robot5.in与robot/robot5.ans. 该样例满足测试点16~18的约束条件。
【数据范围】
