汤姆斯生活在一个等级为 的星球上。那里的环境极其恶劣，每天 小时的工作和成堆的垃圾让人忍无可忍。他向往着等级为 的星球上天堂般的生活。
有一些航班将人从低等级的星球送上高一级的星球，有时需要向驾驶员支付一定金额的费用，有时却又可以得到一定的金钱。
汤姆斯预先知道了从 等级星球去 等级星球所有的航线和需要支付（或者可以得到）的金钱，他想寻找一条价格最低（甚至获得金钱最多）的航线。
第一行一个正整数 （），接下来的数据可分为 个段落，每段的第一行一个整数 （），表示等级为 的星球有 个。
接下来的 行中第 行依次表示与等级为 ，编号为 的星球相连的等级为 的星球的编号和此航线需要的费用（正数表示支出，负数表示收益，费用的绝对值不超过 ）。
每行以 结束，每行的航线数 。
输出所需（或所得）费用。正数表示支出，负数表示收益。
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
对于 的数据，，。
样例解释：
