Description

国王收到了一些投诉，称王国的某些地区在经济上被忽视了。居民们很久没有看到有商人在某些村庄之间的道路上行走。为了改善这一问题，让王国重新繁荣富裕，国王任命了他的皇家数学家制定一份可行的商人路线计划。

该计划要求每条道路上都有正数个商人在某个方向上行走。每个村庄通过道路进入的商人数应等于离开的商人数。为了确保商人在王国各地分布较为均匀，国王要求每条道路上行走的商人数至少为 $1$ 且小于 $M$。

皇家数学家被国王召见，要求他提交研究成果。然而，由于他未能解决这个问题，他的前途未卜。不过，他已经取得了一些进展。他找到了一个每条道路上商人数都合法的方案。唯一的问题是，每个村庄的进出商人数并不完全相等（至少不是严格相等）。它们的差值可能不为零，但对于每个村庄，这个差值模 $M$ 等于零。如果你能编写一个程序，找到一个合法的方案，或者报告不存在这样的方案，他愿意与你分享他的发现。

Input Format

第一行包含三个整数 $N$，表示村庄数，$R$，表示道路数，以及 $M$。

接下来的 $R$ 行，每行包含三个整数 $A_i$、$B_i$ 和 $C_i$，表示有一条从村庄 $A_i$ 到 $B_i$ 的道路，有 $C_i$ 个商人从 $A_i$ 前往 $B_i$。村庄编号为 $1$ 到 $N$。每对村庄之间最多只有一条道路，且没有道路连接同一个村庄。每个村庄的进出商人数之差模 $M$ 等于 $0$。

Output Format

输出每条道路上行走的商人数，按照输入顺序，每行输出一个数。如果商人实际行走方向与输入中道路方向相反，则用负数表示（例如，如果有 $X$ 个商人从 $B_i$ 到 $A_i$ 行走，则第 $i$ 行输出 $-X$）。

如果有多个方案，可以输出任意一个。如果不存在合法方案，输出一行 "IMPOSSIBLE"（不带引号）。

4 5 4
1 2 1
2 3 2
4 1 1
2 4 3
3 4 2

2
3
2
-1
3

Hint

输入范围

• $1 \leq N \leq 1000$
• $0 \leq R \leq 10\,000$
• $2 \leq M \leq 1000$
• $1 \leq A_i, B_i \leq N$
• $0 < C_i < M$

由 ChatGPT 4.1 翻译