B. Иерархия
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
64 megabytes
ввод
stdin
вывод
stdout

В фирму Никиты набрали n человек. Теперь ему нужно построить древовидную иерархию отношений «начальник-подчинённый» в этой фирме (то есть у каждого человека, кроме одного, должен быть ровно один начальник). Дано m заявлений вида «человек ai готов стать начальником человека bi за дополнительную плату ci». Для каждого человека известно его значение квалификации qj, и для каждого заявления выполняется условие qai > qbi.

Помогите Никите определить минимальную стоимость создания иерархии, либо выяснить, что это невозможно.

Входные данные

В первой строке входных данных содержится целое число n (1 ≤ n ≤ 1000) — число сотрудников компании. В следующей строке содержится n чисел qj (0 ≤ qj ≤ 106) записанных через пробел — значения квалификации сотрудников. В следующей строке содержится число m (0 ≤ m ≤ 10000) — количество поданных заявлений. Следующие m строк содержат сами заявления, каждое из которых задаётся тремя числами, записанными через пробел: ai, bi и ci (1 ≤ ai, bi ≤ n, 0 ≤ ci ≤ 106). Заявления могут повторяться, то есть один и тот же сотрудник мог предложить стать начальником другому сотруднику за разные цены. Для каждого заявления qai > qbi.

Выходные данные

В единственной строке выходных данных выведите минимальную стоимость создания иерархии или -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
Примечание

В первом примере один из возможных вариантов составления иерархии — взять заявления под номерами 1, 2 и 4, которые в сумме дадут стоимость 11. Во втором примере составить иерархию невозможно, поэтому ответ -1.