← 返回题目列表

Codeforces · 147/B

B. 微笑之家

中文机器翻译题面 查看原题

创建微笑屋是为了提升心情。它有n个房间。部分房间通过门相连。对于由门连接的每两个房间(编号 i 和 j),Petya 知道它们的值 cij——当他从房间 i 移动到房间 j 时,该值会添加到他的情绪中。

Petya想知道他是否可以无限提升自己的情绪,沿着某个循环移动?如果可以的话,那么在一个周期的一个时期内他需要访问的最少房间数量是多少?

输入

第一行包含两个正整数 n 和 m ($$1 \leq n \leq 300, 0 \leq m \leq \frac{n(n-1)}{2}$$),其中 n 是房间数,m 是微笑屋的门数。然后是门的描述:m 行,每行包含四个整数 i, j, cij и cji (1 ≤ i, j ≤ n, i ≠ j, - 104 ≤ cij, cji ≤ 104)。保证连接任意两个房间的门不超过一扇。没有门将房间与其本身连接起来。

输出

打印在一次循环中需要访问的最小房间数,可以无限提升情绪。如果这样的循环不存在,则打印数字0。

示例

输入 #1

4 4
1 2 -10 3
1 3 1 -10
2 4 -10 -1
3 4 0 -3

输出 #1

4

注意

循环是一系列房间 a1, a2, ..., ak,a1 与 a2 连接,a2 与 a3 连接,...,ak - 1 与 ak 连接,ak 与 a1 连接。序列中的某些元素可以重合,即循环不一定是简单的。循环中的房间数被视为 k,即序列的长度。请注意,最小可能长度等于二。