AT_joig2021_e.パレード (Parade)

为了庆祝 JOIG 的成功举办，JOI 王国计划组织一场鼓笛队的游行。

在 JOI 王国中，有 $N$ 座城市，这些城市被编号为 $1$ 至 $N$。城市之间有 $M$ 条单向道路，编号为 $1$ 至 $M$。第 $i$ 条道路（$1 \leq i \leq M$）连接城市 $A_i$ 和城市 $B_i$，并且该道路是单向的，仅允许从 $A_i$ 通往 $B_i$，道路的长度为 $C_i$。

游行需要满足以下条件：

• 从城市 $1$ 出发，经由多条道路，最终抵达城市 $N$。
• 鼓笛队行走的所有道路长度之和必须不超过 $L$。

作为 JOI 王国的女王，你意识到可能没有可行的路径去满足上述条件。因此，你决定在游行当天反转若干条道路的方向，以便使得游行能够完成。

为避免混乱，应尽量减少需要反转的道路数量。

给定 JOI 王国的城市、道路信息和一个整数 $L$，判断是否可以通过反转某些道路的方向来完成游行。如果可以，输出完成游行所需反转方向的道路的最少数量；如果无法实现，输出 -1。

输入由标准输入给出，格式如下：

$N$ $M$ $L$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\cdots$ $A_M$ $B_M$ $C_M$

输出一行，表示需要反转方向的最少道路数量。如果无论如何反转都无法达到目标，输出 -1。

约束

• $2 \leq N \leq 1000$
• $0 \leq M \leq 1000$
• $1 \leq L \leq 10^9$
• $1 \leq A_i, B_i \leq N$（$1 \leq i \leq M$）
• $A_i \neq B_i$（$1 \leq i \leq M$）
• $(A_i, B_i) \neq (A_j, B_j)$（$1 \leq i < j \leq M$）
• $1 \leq C_i \leq 10^6$（$1 \leq i \leq M$）

所有输入值均为整数。

子任务

1. （7 分）$M = N - 1$，$(A_i, B_i)$ 为 $(i, i + 1)$ 或 $(i + 1, i)$（$1 \leq i \leq M$）。
2. （14 分）$M$ 为偶数，且满足 $A_{2i-1} = B_{2i}$，$A_{2i} = B_{2i-1}$，$C_{2i-1} = C_{2i}$（$1 \leq i \leq \frac{M}{2}$）。
3. （18 分）$N \leq 15$，$M \leq 15$。
4. （20 分）$C_i = 1$（$1 \leq i \leq M$），$L = 10^9$。
5. （20 分）$C_i = 1$（$1 \leq i \leq M$）。
6. （21 分）无特殊约束。

评分说明

所有提交的代码将在评测系统中对所有子任务进行验证。当代码能够针对某个子任务的所有测试用例返回正确结果时，该子任务被标记为完成。每次提交的得分等于成功完成的子任务得分之和。总得分取所有提交的最高得分。

示例解释

1. 若将道路 $1$ 的方向反转，则游行可进行，这是最小反转次数，因此输出 $1$。此例满足子任务 $1, 3, 6$。
2. 无论如何反转道路，游行都无法完成，因此输出 -1。此例满足子任务 $3, 6$。
3. 此例满足子任务 $2, 3, 6$。
4. 此例满足子任务 $3, 4, 5, 6$。
5. 此例满足子任务 $3, 6$。

本翻译由 AI 自动生成