TopCoder

User's AC Ratio

84.6% (11/13)

Submission's AC Ratio

30.1% (22/73)

Tags

Description

TOI 國最近發生了一件重大刑案!警方經過初步的調查,將嫌犯的整個犯罪過程分為 $N$ 個事件,並編號為 $1$ 到 $N$。然而因為現場附近沒有監視器,警方沒有強力的證據能夠推斷這些事件發生的順序以及確切時間。幸好在現場有許多目擊者,而且每位目擊者都看到了至少兩個事件,可以協助警方調查整個犯罪過程。

由於已經過了一段時間,這些目擊者沒辦法記得確切的事件發生順序,只能提供如「事件 $a$ 最晚發生在事件 $b$ 前 $d$ 秒」這樣的證詞($d$ 有可能是負的,可以理解成「事件 $a$ 最晚發生在事件 $b$ 後 $-d$ 秒」)。另外,這些目擊者也不完全可信,因此有可能會發生不同目擊者的證詞彼此矛盾的情況。

為了協助警方調查,請你寫一個程式,根據這些目擊者的證詞輸出一組可能的事件發生時間,或判斷證詞是否有矛盾的情況,以方便警方重建犯罪過程,並過濾這些目擊者的證詞。

Input Format

第一行有兩個正整數 $N,M$,代表整個犯罪過程有 $N$ 個事件,並且目擊者總共提供了 $M$ 個證詞。
接下來有 $M$ 行,每行有三個整數 $a_i, b_i, d_i$,代表第 $i$ 個證詞是「事件 $a_i$ 最晚發生在事件 $b_i$ 前 $d_i$ 秒」。

對於所有測資,$2\leq N \leq 1000; M \leq 5\times 10^ 5; 1\leq a_i,b_i\leq N; a_i\neq b_i; -10\leq d_i\leq 10$。

Output Format

如果目擊者的證詞有任何矛盾的情況,請輸出一行 -1;否則請輸出 $N$ 行,第 $i$ 行有一個整數 $t_i$,代表第 $i$ 個事件發生在第 $t_i$ 秒是一組符合所有目擊者訊息的解。輸出的 $t_i$ 必須滿足 $|t_i| \leq 10^ 6$。

Sample Input

# Sample Input 1
3 2
1 2 2
2 3 2

# Sample Input 2
2 2
1 2 1
2 1 1

Sample Output

# Sample Output 1
0
2
1000

# Sample Output 2
-1

Hints

Problem Source

改編自 NWERC 2011 pG
Problem Set by Yihda Yol

Subtasks

No. Testdata Range Score
1 0~11 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 131072 65536 1
1 2000 131072 65536 1
2 2000 131072 65536 1
3 2000 131072 65536 1
4 2000 131072 65536 1
5 2000 131072 65536 1
6 3000 131072 65536 1
7 3000 131072 65536 1
8 3000 131072 65536 1
9 3000 131072 65536 1
10 2000 131072 65536 1
11 2000 131072 65536 1