#215146. [UOI 2019 II Stage] 土豆

众所周知，波托科兰迪亚由 个城市组成，通过 条单向道路连接。城市编号从 到 。在编号为 的城市中，有 袋土豆。对于每条道路，已知一个整数值 —— 哥萨克通过该道路搬运一袋土豆所需的时间。不同道路的 值可能不同。可以认为，每个城市都有数量极多的哥萨克，并且可以同时搬运任意数量的土豆袋。

哥萨克胡子得知，一种将摧毁土豆的病毒很快将进入波托科兰迪亚。为了保护收成，哥萨克们打算将土豆藏入地下掩体。

全国共有 个掩体，编号从 到 。编号为 的掩体位于编号为 的城市，可以保护最多 袋土豆免受病毒侵害。

现在我们的英雄想知道，哥萨克们将所有土豆袋藏入掩体所需的最短时间。请帮助他完成这个任务！

第一行包含三个整数 、 和 (, , ) —— 分别表示波托科兰迪亚的城市数量、道路数量和掩体数量。

第二行包含 个整数 () —— 各城市中的土豆袋数量。

接下来的 行描述道路，每行包含三个整数 、、 (, , ) —— 表示相应道路连接的城市编号，以及哥萨克通过该道路搬运一袋土豆所需的时间。编号为 的道路允许从城市 移动到城市 。保证对于任意 ，最多存在一条从城市 到城市 的道路。

接下来的 行描述掩体，每行包含两个整数 和 (, ) —— 表示相应掩体所在的城市编号，以及该掩体能够保护免受病毒侵害的最大土豆袋数量。

输出一个整数 —— 哥萨克们将所有土豆袋藏入掩体所需的最短时间。如果无法将所有土豆袋藏入掩体，则输出 。

样例输入 1

2 1 1
3 2
2 1 4
1 6

样例输出 1

4

样例输入 2

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

样例输出 2

7

样例输入 3

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

样例输出 3

22

第一个样例的解释：

可以将所有土豆袋藏入掩体。为此，只需将两袋土豆从编号 的城市搬运到编号 的城市。

第二个样例的解释：

需要在每个掩体中各藏 袋土豆。为此，只需将两袋土豆从编号 的城市搬运到编号 的城市，并将两袋土豆从编号 的城市搬运到编号 的城市（后者的搬运最好按以下路线进行： ）。

特殊性质 A：对于任何一条从城市 到城市 的道路，都存在一条从城市 到城市 的道路，并且这两条道路的权重 相等。

:::align{center} :::

翻译由 DeepSeek V3 完成