汤姆斯的天堂梦

题目描述

汤姆斯生活在一个等级为 $0$ 的星球上。那里的环境极其恶劣,每天 $12$ 小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为 $N$ 的星球上天堂般的生活。 有一些航班将人从低等级的星球送上高一级的星球,有时需要向驾驶员支付一定金额的费用,有时却又可以得到一定的金钱。 汤姆斯预先知道了从 $0$ 等级星球去 $N$ 等级星球所有的航线和需要支付(或者可以得到)的金钱,他想寻找一条价格最低(甚至获得金钱最多)的航线。

输入输出格式

输入格式


第一行一个正整数 $N$($N \le 100$),接下来的数据可分为 $N$ 个段落,每段的第一行一个整数 $K_i$($K_i \le 100$),表示等级为 $i$ 的星球有 $K_i$ 个。 接下来的 $K_i$ 行中第 $j$ 行依次表示与等级为 $i$,编号为 $j$ 的星球相连的等级为 $i - 1$ 的星球的编号和此航线需要的费用(正数表示支出,负数表示收益,费用的绝对值不超过 $1000$)。 每行以 $0$ 结束,每行的航线数 $\le 100$。

输出格式


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

输入输出样例

输入样例 #1

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

-1

说明

对于 $100 \%$ 的数据,$1 \le N \le 100$,$1 \le K_i \le 100$。 样例解释: ![](https://cdn.luogu.com.cn/upload/image_hosting/x085ukra.png)