题目描述
花国的餐厅有 $n$ 个，作为美食家的你希望用最少的钱 $f_i$ 吃到花城的 $i$ 个餐厅。
这里第 $i$ 个餐厅老板有若干个喜欢的餐厅 $v_1,v_2,\cdots,v_{d_i}$，当然这里不包括自己。
第 $u$ 个餐厅的老板会推荐第 $v$ 个餐厅当且仅当：存在一个序列 $a_1,a_2,\cdots, a_k, a_1=u,a_k=v, \forall 1 \le i < k$, 第 $a_i$ 个餐厅的老板 喜欢 第 $a_{i+1}$ 个餐厅。
对于你在花国的旅程，会经过以下事件。
- 你可以从任意餐厅开始你的旅程
- 当你到达一个餐厅 $i$，如果你持有这个餐厅老板推荐的店的用餐记录，你必须支付 $x_i$ 块钱，否则需要支付 $y_i$ 块钱。
- 当你在餐厅 $i$ 支付后并餐过后，你会获得一个来自第 $i$ 个店的用餐记录，并且你去往的下一个餐厅必须是当前老板推荐的没去过的餐厅。
- 你可以在在任意餐厅用餐后终止旅程。
令 $K$ 表示你最多可以吃到多少个餐厅，求 $f_1, f_2, \cdots, f_K$，表示吃到了 $i$ 个餐厅的最小花费。
输入格式
第一行一个正整数 $n$。
接下来 $n$ 行，输入 $x_i,y_i,d_i,v_1,v_2,\cdots,v_{d_i}$，表示这个餐厅的两种价钱，老板喜欢的餐厅个数，以及它们的编号。
输出格式
输出 $K$ 行，每行一个数表示 $f_i$。
样例数据
样例 1 输入
4
100 200 1 2
200 300 1 3
200 250 2 2 4
200 300 0样例 1 输出
200
450
650
950样例 2 输入
9
100 100 0
300 400 1 4
350 500 1 2
550 600 3 7 3 2
900 300 2 7 6
250 400 1 5
900 900 2 9 8
400 500 1 9
500 400 0样例 2 输出
100
550
950
1450
2150
3050样例 3
见下发文件中的 ex_trip3.in/ex_trip3.ans。
子任务
请注意，本题的满分为 7 分。
对于所有数据：保证 $1\le n \le 1000,1\le x_i,y_i\le 10^4,0\le d_i < n$。