477 . 芽芽逛大街
Description
芽芽喜歡到處亂逛街，每走到一個景點他就能透過欣賞得到該景點的美麗值，而每經過一條景點與景點之前連接的道路他也能透過欣賞得到該道路的美麗值。
但芽芽是一個喜新厭舊的人，凡是他欣賞過的景點或街道，叫他再欣賞一次他欣賞過的東西他就會感到無聊而得不到任何美麗值。
現在他來到了一個非常具有特色的國家，這個國家有 $N$ 個景點，並由 $M$ 條單向的道路互相連接著。由於芽芽打算自由選擇一個景點出發後，沿著道路經過各式各樣的景點並停在另一個任意的景點，他想知道在所有可行的方案當中，若採取最佳的策略，他可以得到總和多大的美麗值，你可以寫一支程式幫助他嗎？
Input Format
測試資料第一行包含兩個非負整數 $N,M(1\le N\le 5\times 10^5,0\le M\le 5\times 10^5)$，代表芽芽抵達的國家有 $N$ 個景點，$M$ 條單向的道路。
接下來一行 $N$ 個非負整數 $s_1,\cdots,s_N(0\le s_i\le 10^9)$，代表芽芽如果走到景點 $i$，他就可以透過欣賞得到 $s_i$ 的美麗值。
接下來 $M$ 行，第 $i$ 行三個非負整數 $u_i,v_i,w_i(1\le u_i,v_i\le N,u_i\ne v_i,0\le w_i\le 10^9)$，代表該國家的第 $i$ 條單向道路讓景點 $u_i$ 可以抵達 $v_i$，且若芽芽經過該條道路，他可以透過欣賞得到 $w_i$ 的美麗值。
Output Format
輸出一行一個整數，代表芽芽在採取最佳策略下，他可以得到總和多大的美麗值。
Sample Input 1
7 6
3 6 2 6 7 0 1
1 2 1
2 3 4
2 4 2
1 5 7
3 6 0
6 7 1
3 6 2 6 7 0 1
1 2 1
2 3 4
2 4 2
1 5 7
3 6 0
6 7 1
Sample Output 1
18
Sample Input 2
8 10
4 8 0 5 9 2 4 1
1 3 5
2 1 0
4 1 0
4 2 6
3 4 1
1 4 7
8 2 3
7 1 5
3 5 2
4 6 8
4 8 0 5 9 2 4 1
1 3 5
2 1 0
4 1 0
4 2 6
3 4 1
1 4 7
8 2 3
7 1 5
3 5 2
4 6 8
Sample Output 2
56
Sample Input 3
7 8
2 7 5 6 4 3 3
1 4 9
5 4 6
4 6 5
4 6 1
3 7 5
2 6 2
5 2 7
1 6 3
2 7 5 6 4 3 3
1 4 9
5 4 6
4 6 5
4 6 1
3 7 5
2 6 2
5 2 7
1 6 3
Sample Output 3
25
Sample Input 4
10 16
3 1 4 1 5 9 2 6 5 3
1 2 5
2 3 8
3 1 9
4 5 7
5 4 9
6 7 3
7 8 2
8 6 3
9 10 8
10 9 4
3 6 6
2 7 2
3 10 6
4 7 4
5 7 3
4 9 3
3 1 4 1 5 9 2 6 5 3
1 2 5
2 3 8
3 1 9
4 5 7
5 4 9
6 7 3
7 8 2
8 6 3
9 10 8
10 9 4
3 6 6
2 7 2
3 10 6
4 7 4
5 7 3
4 9 3
Sample Output 4
61
Hints
Problem Source
NEOJ Problem 739
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0, 4~10 | $M=N-1$、$u_i\le i, v_i=i+1$ | 20 |
| 2 | 1, 4~19 | 沒有任何景點可以透過一連串的道路走回自己 | 20 |
| 3 | 0~3, 20~33 | $1\le N,M\le 5000$ | 20 |
| 4 | 0~47 | 無特別限制 | 40 |