eolymp
bolt
Try our new interface for solving problems
Problems

Операция "Стейк или кипячение"

Операция "Стейк или кипячение"

Time limit 2 seconds
Memory limit 256 MiB

Маркетологи компании "std::steak" разработали новый рекламный проект "Стейк или кипячение". Суть проекта заключается в захвате рынка всей Берляндии. Группы агентов будут заходить в каждый дом каждого города и задавать глупый вопрос: "Стейк или кипячение?". Таким образом компания расчитывает полностью повергнуть в ужас всех конкурентов и озадачить потенциальных покупателей.

Высадка групп агентов произойдёт в некоторых городах Берляндии с воздуха. Далее по дорогам агенты должны посетить все города страны. Города соединены односторонними дорогами, для каждой дороги задана её длина. В каждом городе группы могут делится произвольным образом (количество человек в группе изначально чрезвычайно велико).

Известно, что затраты на перемещение по дороге равны её длине. Для каждого города известна стоимость организации высадки десанта в него.

Какой наименьший бюджет может иметь операция "Стейк или кипячение"?

Input data

Входной файл состоит из одного или нескольких наборов входных данных.

В первой строке каждого набора записана пара целых чисел N, M (1N300, 0MN^2-N), где N - количество городов в Берляндии, а M - количество дорог. Во второй строке записана последовательность A_1, A_2, ..., A_N, где A_i- стоимость высадки десанта в пукт i (1A_i1000). Далее в M строках описаны дороги тройками чисел X_i, Y_i, L_i, где X_i - стартовый город дороги, Y_i - конечный, а L_i - её длина (1X_i, Y_iN, X_iY_i, 1L_i1000). Между каждой парой городов существует не более одной дороги в каждом направлении.

Сумма значений N по всем наборам входных данных не превосходит 300.

Output data

Для каждого набора входных данных выведите искомый наименьший бюджет.

Examples

Input example #1
2 2
4 8
1 2 7
2 1 2
3 2
1 8 4
1 2 7
2 1 2
7 9
4 8 6 10 1 4 10
2 4 6
2 6 3
3 1 1
3 5 10
3 6 8
5 6 8
7 2 6
7 3 4
7 4 2
Output example #1
10
12
27