bzoj#P2163. 复杂的大门

复杂的大门

题目描述

你去找某 bm 玩,到了门口才发现要打开他家的大门不是一件容易的事……

他家的大门外有 nn 个站台,用 11nn 的正整数编号。你需要对每个站台访问一定次数以后大门才能开启。站台之间有 mm 个单向的传送门,通过传送门到达另一个站台不需要花费任何代价。而如果不通过传送门,你就需要乘坐公共汽车,并花费 11 单位的钱。值得庆幸的是,任意两个站台之间都有公共汽车直达。

现在给你每个站台必须访问的次数 fif_i,对于站台 ii,你必须恰好访问 fif_i 次(不能超过)。 我们用 u,v,wu,v,w 三个参数描述一个传送门,表示从站台 uu 到站台 vv 有一个最多可以使用 ww 次的传送门(不一定要使用 ww 次)。值得注意的是,对于任意一对传送门 (u1,v1)(u_1,v_1)(u2,v2)(u_2,v_2),如果有 u1<u2u_1<u_2,则有 v1v2v_1\leq v_2;如果有 v1<v2v_1<v_2,则有 u1u2u_1\leq u_2;且 u1=u2u_1=u_2v1=v2v_1=v_2 不同时成立。

你可以从任意的站台开始,从任意的站台结束。出发去开始的站台需要花费 11 单位的钱。你需要求出打开大门最少需要花费多少单位的钱。

输入格式

第一行包含两个正整数 n,mn,m,意义见题目描述。

第二行包含 nn 个正整数,第 ii 个数表示 fif_i。接下来有 mm 行,每行有三个正整数 u,v,wu,v,w,表示从 uuvv 有一个可以使用 ww 次的传送门。

输出格式

输出一行一个整数,表示打开大门最少花费的钱数。

样例输入

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

样例输出

17

数据规模与约定

20%20\% 的数据满足 n10n\leq 10m50m\leq 50;对于所有的 w,fiw,f_i,满足 1w,fi101\leq w,f_i\leq 10

50%50\% 的数据满足 n1×103n\leq 1\times 10^3m1×104m\leq 1\times 10^4

100%100\% 的数据满足 1n1×104,1m1×1051\leq n\leq 1\times 10^4,1\leq m\leq 1\times 10^5;对于所有的 u,vu,v,满足 1u,vn1\leq u,v\leq nuvu\neq v;对于所有的 w,fiw,f_i,满足 1w,fi5×1041\leq w,f_i\leq 5\times 10^4

以上的每类数据中都存在 50%50\% 的数据满足对于所有的 w,fiw,f_i,有 w=fi=1w=f_i=1