题目描述

小 $n$ 的公司有 $n$ 个员工，每个员工 $i$ 有一个初始的权值 $q_i$，每一个员工有且只有一个上司。有 $m$ 条申请，每个申请由三个数 $a_i$，$b_i$，$c_i$ 构成，代表将 $a_i$ 任命为 $b_i$ 的上司所需要的花费为$c_i$，同时必须保证 $q_{a_i}>q_{b_i}$。

试求使每个员工（顶头上司除外）都有且只有一个上司所花费的最小代价。

输入格式

第一行 $n$，$1 \le n \le 10^3$。

第二行 $n$ 个数表示 $q_i$，$0 \le q_i \le 10^6$。

第三行 $m$，$0 \le m \le 10^4$。

之后 $m$ 行每行三个数表示$a_i$，$b_i$，$c_i$。$0 \le c_i \le 10^6$，$1 \le a_i,b_i \le n$。

输出格式

一个整数表示最小代价，若无解则输出 -1。

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

11

3
1 2 3
2
3 1 2
3 1 3

-1