题目背景

译自 Italian Olympiad in Informatics (OII) 2025 - Raccogli i lampioni。

OII 纪念碑的建造场地终于被清理干净了！工作人员现在需要考虑的是该区域的照明工作。购买新的路灯是不可能的，因为大部分资金都花在了木材运输上。一个更现实的方案是从乌迪内市借用一些路灯。

题目描述

乌迪内市有 $N$ 个路口，被 $M$ 条双向道路所连接。在路口 $i(0\le i<N)$，有一盏高度为 $H_i$ 的路灯。第 $j(0\le j<M)$ 条道路连接编号为 $A_j$ 和 $B_j$ 的路口，长度为 $L_j$。

要借用一盏路灯 $H_i$，必须将其放倒在一条连接了路口 $i$ 的道路上，前提是这条路上要有足够的空间：也就是说，放倒在第 $j$ 条道路上的路灯长度之和不能超过 $L_j$。

请帮助工作人员确定能借用的最大路灯数量。

• 两个路口之间可能有多于一条道路。此外，不能保证每个路口都可以通过道路与其他所有路口相连。

实现细节

附件中包含一个实现示例 benilluminato.cpp。

你需要实现如下函数：

int illumina(int N, int M, vector<int> H, vector<int> A, vector<int> B, vector<int> L);

• 整数 $N$：路口的数量。
• 整数 $M$：道路的数量。
• 数组 $H$：下标从 $0$ 到 $N-1$，包含每个路口上路灯的高度。
• 数组 $A,B$ 和 $L$：下标从 $0$ 到 $M-1$，描述了道路，其中第 $j$ 条道路连接路口 $A_{j}$ 和 $B_{j}$，长度为 $L_{j}$ 米。
• 该函数需要返回能借用的最大路灯数量。
• 对于每个测试点，该函数都只会被调用一次。

输入格式

评测程序的输入格式如下：

• 第 $1$ 行：两个整数 $N$ 和 $M$。
• 第 $2$ 行：$N$ 个整数 $H_0,H_1,\ldots,H_{N-1}$。
• 第 $2 + j$ 行（$0 \le j < M$）：三个整数 $A_j,B_j,L_j$。

输出格式

评测程序的输出格式如下：

输出一行一个整数，表示函数 illumina 的返回值。

4 3
4 2 3 3
0 1 4
0 2 6
0 3 8

4

8 10
3 2 3 2 4 6 5 9
0 1 4
1 2 1
2 3 3
3 4 1
0 4 8
2 5 8
3 5 7
1 6 4
5 7 3
6 7 10

7

2 2
5 6
0 1 5
0 1 9

2

提示

【样例解释】

在样例 1 中，如下的方案可以最大化借用的路灯数量（可以借用所有路灯）：

• 将路灯 $0$ 和路灯 $3$ 放倒在道路 $2$ 上；
• 将路灯 $1$ 放倒在道路 $0$ 上；
• 将路灯 $2$ 放倒在道路 $1$ 上。

在样例 2 中，如下的方案可以最大化借用的路灯数量（不能借用所有的 $8$ 盏路灯，但是可以借用 $7$ 盏）：

• 将路灯 $0$ 和路灯 $4$ 放倒在道路 $4$ 上；
• 将路灯 $1$ 放倒在道路 $0$ 上；
• 将路灯 $2$ 放倒在道路 $5$ 上；
• 将路灯 $3$ 放倒在道路 $2$ 上；
• 将路灯 $5$ 放倒在道路 $6$ 上；
• 将路灯 $6$ 放倒在道路 $9$ 上。

在样例 3 中，如下的方案可以最大化借用的路灯数量（可以借用所有路灯）：

• 将路灯 $0$ 放倒在道路 $0$ 上；
• 将路灯 $1$ 放倒在道路 $1$ 上。

【数据范围】

• $1\le N,M\le 10^6$；
• $1\le H_i\le 1000$；
• $0\le A_j,B_j<N$ 且 $A_j\neq B_j$；
• $1\le L_j\le 2000$。

【子任务】

子任务编号	分值	约束条件
$0$		样例
$1$	$6$	$N,M\le 10$
$2$	$11$	$M=N-1$，$A_j=j$，$B_j=j+1$ 且 $H_i=1$
$3$	$16$	$M=N-1$，$A_j=j$，$B_j=j+1$
$4$	$27$	$H_i=1$ 且 $L_j=1$
$5$	$12$	$H_i=1$
$6$	$28$	无额外限制