P12474 [集训队互测 2024] 生命的循环

生命是一张由 $n$ 个神经节点与 $m$ 条神经构成的**带权**有向图，允许存在**自环**、**重边**。 一条编号为 $i$ 的神经 $(u_i, v_i, w_i)$ **单向地**连接着两个神经节点 $u_i \rightarrow v_i$，长度为 $w_i$。 生命的网络不会过于复杂，对于任意一条**简单回路**，其包含的所有神经长度之和**不大于**一个定值 $B$。 神经节点在某些时刻会兴奋，定义 $f(u, t)$ 表示 $t$ 时刻神经节点 $u$ 是否处于兴奋状态。 兴奋会沿着神经传导，对于第 $i$ 条神经 $(u_i, v_i, w_i)$，若神经节点 $u_i$ 在时刻 $t$ 是兴奋的，那么其会向节点 $v_i$ 传递神经信号，使其在时刻 $t + w_i$ 进入兴奋状态。 神经节点的兴奋状态**不会保留**到下一个时刻，即神经节点 $u$ 在进入兴奋状态后会沿其它神经立刻向外传递神经信号；接下来的时刻里，如果没有其它神经向它传递神经信号，则该神经节点会**保持不兴奋**的状态。 如果在**同一个时刻**，一个节点进入兴奋状态后其递归地向自身传递了神经信号，兴奋状态也不会保留到下一个时刻。（换句话说，数据中存在边权和为 0 的简单回路，此时你可以将整条简单回路等效地看作单个神经节点处理。） 生命的伊始，神秘的力量刺激了 1 号神经节点，使其在**时刻 0** 时进入兴奋状态。从此开始无数的时间里，生命的讯号便在神经网络中不息传递着。 在经过葛立恒数个时刻的洗礼后，一位实力强大的 Oler——你，历经千辛万苦，终于抵达了 $n$ 号神经节点。在那里，你看到生命总是趋于循环。 即，保证经过充分长的时间后，$n$ 号神经节点以一个固定时间周期依据一定模式重复进入兴奋状态。 现在的你开始好奇，**此时** $n$ 号神经节点的进入兴奋状态的**最小周期**是多少？ 亦即，你需要求出一个最小的正整数 $p$，满足存在一个**有限**的非负整数 $M$，使得 $$\forall x \geq M, f(n, x) = f(n, x + p)$$ 由于 $p$ 可能很大，你只需要输出 $p$ 对 $10^9 + 9$ **取模**后的结果。

第一行输入三个数 $n, m, type$，依次表示神经节点个数、神经条数、子任务编号。你可以通过 $type$ 来判断 $B$ 的取值。特别地，对于题面中的样例，$type = 0$。 接下来 $m$ 行，第 $i$ 行三个数 $u_i, v_i, w_i$，描述第 $i$ 条神经由神经节点 $u_i$ 指向神经节点 $v_i$，长度为 $w_i$。

输出一行一个正整数，表示答案 $p$ 对于 $10^9 + 9$ 取模后的结果。

### 数据约束 对于所有数据满足 $2 \leq n \leq 5000, 0 \leq m \leq 10^4, 1 \leq u_i, v_i \leq n, 0 \leq w_i \leq B \leq 100$。 ### 子任务 - Subtask 1 (1 pts): 神经构成的有向图是一张 DAG，即不存在任何简单回路。 - Subtask 2 (8 pts): $n, B \leq 10, m \leq 15$。 - Subtask 3 (11 pts): 原图强连通。即任意一对神经节点间都可以通过神经组成的有向路径互相可达。 - Subtask 4 (10 pts): 存在至少一条包含点 $n$ 的简单回路。 - Subtask 5 (19 pts): 所有的简单回路点集互不相交，且总长度两两互质。 - Subtask 6 (9 pts): 所有的简单回路点集互不相交，且总长度均为质数的若干次幂。 - Subtask 7 (18 pts): $B \leq 30$。 - Subtask 8 (24 pts): 无特殊限制。