#P1796. 汤姆斯的天堂梦

汤姆斯的天堂梦

题目描述

汤姆斯生活在一个等级为 00 的星球上。那里的环境极其恶劣,每天 1212 小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为 NN 的星球上天堂般的生活。

有一些航班将人从低等级的星球送上高一级的星球,有时需要向驾驶员支付一定金额的费用,有时却又可以得到一定的金钱。

汤姆斯预先知道了从 00 等级星球去 NN 等级星球所有的航线和需要支付(或者可以得到)的金钱,他想寻找一条价格最低(甚至获得金钱最多)的航线。

输入格式

第一行一个正整数 NNN100N \le 100),接下来的数据可分为 NN 个段落,每段的第一行一个整数 KiK_iKi100K_i \le 100),表示等级为 ii 的星球有 KiK_i 个。

接下来的 KiK_i 行中第 jj 行依次表示与等级为 ii,编号为 jj 的星球相连的等级为 i1i - 1 的星球的编号和此航线需要的费用(正数表示支出,负数表示收益,费用的绝对值不超过 10001000)。

每行以 00 结束,每行的航线数 100\le 100

输出格式

输出所需(或所得)费用。正数表示支出,负数表示收益。

3
2
1 15 0
1 5 0
3
1 -5 2 10 0
1 3 0
2 40 0
2
1 1 2 5 3 -5 0
2 -19 3 -20 0
-1

提示

对于 100%100 \% 的数据,1N1001 \le N \le 1001Ki1001 \le K_i \le 100

样例解释: