# 旅游安排

- 参考时间限制：**6.0 秒**（[评测环境与性能](../../../docs/评测环境与性能.md)）。
- 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 2，再按 0.5 秒向上取整。
- 内存限制：**128 MB**。

## 背景故事

方块小镇准备组织一次村际旅行。居民只对离家较近的村子感兴趣，各村接待游客的名额也有限。旅行中的消费太多还会拖慢服务器，因此组织者希望先让尽可能多的人出游，再尽量降低总消费。

小镇有些旅游道路带有时间旅行装置，记录的距离可能是负数。请先检查道路是否存在负环，再安排游客。

## 形式化问题描述

有 $n$ 个村子和 $m$ 条有向道路。道路 $u\to v$ 的长度为 $w$ . 若道路图的任意位置存在总长度为负的有向环，直接报告负环。

否则，令 $d(i,j)$ 为从村子 $i$ 到村子 $j$ 的最短路长度。村子 $i$ 的候选目的地为所有可从 $i$ 到达且不同于 $i$ 的村子。按数对

$$\bigl(d(i,j),\lvert i-j\rvert\bigr)$$

从小到大排序，先比较最短路长度，再比较编号差的绝对值。村子 $i$ 的居民对前 $k_i$ 个候选目的地感兴趣；若第 $k_i$ 名与后面的目的地在这两个量上都相同，并列者全部入选。候选目的地不足 $k_i$ 个时全部入选；$k_i=0$ 时没有感兴趣的目的地。

村子 $i$ 有 $V_i$ 名希望旅行的居民，每人出游会消费 $C_i$ 次。村子 $j$ 最多接待 $H_j$ 名外来游客，每次消费的价格为 $P_j$ . 一名村子 $i$ 的居民前往村子 $j$ 时，产生 $C_iP_j$ 的费用。

每位居民最多前往一个自己感兴趣的目的地。未出游者留在本村，不占接待名额，也不产生费用。道路只用于确定目的地的远近，不限制游客流量，也不额外收费。

在出游人数最大化的前提下，求总费用的最小值。

## 输入格式

第一行两个整数 $n,m$ .

接下来 $m$ 行，每行三个整数 $u,v,w$ ，表示一条从 $u$ 到 $v$ 的有向道路。

接下来 $n$ 行，第 $i$ 行五个整数 $k_i,V_i,C_i,H_i,P_i$ .

## 输出格式

若道路图存在负环，输出一行 `Negative loop found.`（包括末尾英文句号）。否则输出一行整数，表示最大出游人数下的最小总费用。没有人能够出游时输出 $0$ .

## 样例 1

### 输入

```text
4 6
1 2 1
1 3 2
1 4 3
2 3 -1
2 4 3
3 4 7
3 3 2 0 0
2 2 3 2 5
1 4 1 2 3
0 0 0 1 10
```

### 输出

```text
45
```

## 样例 2

### 输入

```text
2 2
1 2 1
2 1 -2
3 3 2 0 0
2 2 3 2 5
```

### 输出

```text
Negative loop found.
```

## 样例 3

### 输入

```text
3 2
2 1 1
2 3 1
0 0 0 1 7
1 2 1 0 0
0 0 0 1 11
```

### 输出

```text
18
```

## 样例解释

样例 1 的总接待名额为 $5$ . 让村子 $1$ 向村子 $2$ 派 $2$ 人、向村子 $3$ 派 $1$ 人，再让村子 $2$ 向村子 $3$ 派 $1$ 人、村子 $3$ 向村子 $4$ 派 $1$ 人，便可安排 $5$ 人出游，总费用为 $20+6+9+10=45$ .

样例 2 的环 $1\to2\to1$ 总长度为 $-1$ .

样例 3 中，村子 $1$ 和 $3$ 对村子 $2$ 的排名并列，即使 $k_2=1$ ，二者仍都入选。两名游客各去一个目的地，总费用为 $7+11=18$ .

## 数据范围与保证

对 100% 的数据：$1\le n\le1000$ ，$1\le m\le5000$ ；每条道路满足 $1\le u,v\le n$ 、$u\ne v$ 、$-10^9\le w\le10^9$ . 允许多条道路连接同一对有序端点。

对每个村子：$0\le k_i\le10$ ，$0\le V_i,H_i\le10^9$ ，$0\le C_i,P_i\le30$ . 所有输入量均为整数。

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |