A - 倉庫の在庫管理 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君は、ある会社の物流部門で働いています。会社には N 個の倉庫があり、倉庫 1 から倉庫 N まで番号が付けられています。各倉庫 i (1 \leq i \leq N) には現在 P_i 個の商品が保管されています。

本日、倉庫間で商品を移動させる M 件の配送指示が出されました。j 番目 (1 \leq j \leq M) の配送指示は「倉庫 U_j から倉庫 V_j へ W_j 個の商品を移動させる」という内容です。ここで、U_j \neq V_j です。同じ倉庫ペア間の配送指示が複数存在することもあります。

M 件の配送指示は逐次的にではなく一括で反映されます。すなわち、各倉庫の最終的な商品数は、初期の商品数に対して、その倉庫に入ってくる商品数の合計を加え、その倉庫から出て行く商品数の合計を引いたものです。

高橋君は、すべての配送指示を反映した後に商品数が最も多い倉庫の番号を求めたいです。商品数が最も多い倉庫が複数ある場合は、その中で番号が最も小さい倉庫の番号を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j \leq N (1 \leq j \leq M)
  • 1 \leq V_j \leq N (1 \leq j \leq M)
  • U_j \neq V_j (1 \leq j \leq M)
  • 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
  • すべての入力値は整数である
  • すべての配送指示を反映した後、各倉庫の商品数は 0 以上になることが保証される

入力

N M
P_1 P_2 \ldots P_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • 1 行目には、倉庫の数 N と配送指示の数 M が、スペース区切りで与えられる。
  • 2 行目には、各倉庫の初期の商品数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
  • 続く M 行では、各配送指示の内容が与えられる。M = 0 の場合、この部分は与えられない。
  • そのうち j 行目 (1 \leq j \leq M) では、j 番目の配送指示における移動元の倉庫番号 U_j、移動先の倉庫番号 V_j、移動する商品数 W_j が、スペース区切りで与えられる。

出力

すべての配送指示を反映した後に商品数が最も多い倉庫の番号を 1 行で出力してください。最も多い倉庫が複数ある場合は、番号が最も小さいものを出力してください。

入力例 1

3 2
10 20 30
1 2 5
3 2 10

出力例 1

2

入力例 2

3 2
10 20 10
2 1 5
2 3 5

出力例 2

1

入力例 3

6 5
100 200 150 300 250 50
4 2 50
1 3 30
5 6 100
2 1 80
3 5 40

出力例 3

4

入力例 4

10 8
500 300 800 200 600 100 450 350 700 250
3 1 200
5 7 150
9 2 300
4 6 100
1 10 400
8 3 50
7 9 100
6 5 50

出力例 4

3

入力例 5

1 0
1000000000

出力例 5

1

Score : 266 pts

Problem Statement

Takahashi works in the logistics department of a company. The company has N warehouses, numbered from warehouse 1 to warehouse N. Each warehouse i (1 \leq i \leq N) currently stores P_i items.

Today, M shipping instructions to move items between warehouses have been issued. The j-th (1 \leq j \leq M) shipping instruction is "move W_j items from warehouse U_j to warehouse V_j." Here, U_j \neq V_j. There may be multiple shipping instructions between the same pair of warehouses.

The M shipping instructions are applied all at once, not sequentially. That is, the final number of items in each warehouse is obtained by taking the initial number of items, adding the total number of items coming into that warehouse, and subtracting the total number of items going out of that warehouse.

Takahashi wants to find the warehouse number with the most items after all shipping instructions have been applied. If there are multiple warehouses with the most items, find the one with the smallest warehouse number.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq P_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq U_j \leq N (1 \leq j \leq M)
  • 1 \leq V_j \leq N (1 \leq j \leq M)
  • U_j \neq V_j (1 \leq j \leq M)
  • 1 \leq W_j \leq 10^9 (1 \leq j \leq M)
  • All input values are integers.
  • It is guaranteed that after all shipping instructions have been applied, the number of items in each warehouse is 0 or more.

Input

N M
P_1 P_2 \ldots P_N
U_1 V_1 W_1
U_2 V_2 W_2
\vdots
U_M V_M W_M
  • The first line contains the number of warehouses N and the number of shipping instructions M, separated by a space.
  • The second line contains the initial number of items in each warehouse P_1, P_2, \ldots, P_N, separated by spaces.
  • The following M lines contain the details of each shipping instruction. If M = 0, this part is not given.
  • The j-th line (1 \leq j \leq M) contains the source warehouse number U_j, the destination warehouse number V_j, and the number of items to move W_j for the j-th shipping instruction, separated by spaces.

Output

Print on one line the warehouse number with the most items after all shipping instructions have been applied. If there are multiple warehouses with the most items, print the one with the smallest number.

Sample Input 1

3 2
10 20 30
1 2 5
3 2 10

Sample Output 1

2

Sample Input 2

3 2
10 20 10
2 1 5
2 3 5

Sample Output 2

1

Sample Input 3

6 5
100 200 150 300 250 50
4 2 50
1 3 30
5 6 100
2 1 80
3 5 40

Sample Output 3

4

Sample Input 4

10 8
500 300 800 200 600 100 450 350 700 250
3 1 200
5 7 150
9 2 300
4 6 100
1 10 400
8 3 50
7 9 100
6 5 50

Sample Output 4

3

Sample Input 5

1 0
1000000000

Sample Output 5

1