创建微笑屋是为了提升心情。它有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,即序列的长度。请注意,最小可能长度等于二。