3613. 旅游纪念

【题目背景】

有一个憨厚的小孩子叫 Ph，他非常喜欢旅行，每次旅行都要买一个纪念品，当然，他还要卖掉这个纪念品，从而赚得差价，赚回一点旅费。

【题目描述】

Ph 要从城市 1 出发，终点是城市 $n$，有 $m$ 条单向道路，过这些道路需要花费一定的费用。

Ph 决定了他要买某一种纪念品，他经过调查得知了此纪念品在每个城市的价格。他可以在任何一个城市购买纪念品，然后在任何一个城市卖出，必须买一次（即使亏损，也要让亏损最小），但是最多只能购买一次。现在他想请你帮忙求出他这次旅行的最小费用（路费-纪念品赚的差价），可能是个负数。

【输入格式】

第一行，包含 2 个正整数 $n$ 和 $m$，分别表示城市个数和城市间道路数。

接下来 $m$ 行，每行用三个正整数 $x,y,z$ 表示从城市 $x$ 到 $y$ 有一条路费为 $z$ 的道路。

最后一行，包含 $n$ 个数字，第 $i$ 个数字 $v_i$ 表示城市 $i$ 的纪念品价值。

【输出格式】

一个整数，表示最小费用；

【样例输入】

5 7
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
5 4 2
3 2 2
4 3 5 6 1

【样例输出】

1

【样例说明】

路线 $1\to 4\to 5$，在城市 1 买入，到达城市 4 时卖出纪念品，赚得旅费为 2，路费共花去 3，最小费用为 $3-2=1$。

【数据规模与约定】

对于 $100\%$ 的数据：$1 \le n \le 5\times 10^4，1 \le m \le 10^5,1\le v_i \le 100，1 \le z \le 100，1 \le x,y \le n$。

【来源】

cb@sywb

20211018 实验文博桐柏一中普及组联赛