该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

描述

尼克的公司有 n 个员工，每个员工 i有一个初始的权值 $q_i$ ，每一个员工有且只有一个上司。 有 m条申请，每个申请由三个数 $a_i$，$b_i$，$c_i$构成，代表将 $a_i$ 任命为 $b_i$ 的上司所需要的花费为$c_i$，同时必须保证 $q_{a_i}>q_{b_i}$（$a_i$的权值必须大于$b_i$的）。试求使每个员工(顶头上司除外)都有且只有一个上司所花费的最小代价。

你会帮助尼克计算这样一个层次结构的最小代价，若无解则输出-1。

输入格式

第一行 n，第二行 n 个数表示 $q_i$，第三行 m，之后 m 行每行三个数表示$a_i$ ，$b_i$，$c_i$。

输出格式

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

说明/提示

数据规模与约定

$1≤n≤10^3，0≤m≤10^4, 0≤q_i≤10^6，0≤c_i≤10^6，1≤a_i,b_i≤n$ 。

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

样例解释

样例1：1成为2和3的上司，花费10，2成为4或3成为4的上司，花费1，共花费11。

样例2：2和其他没有申请所以没有解，输出-1。