Операция "Стейк или кипячение"
Маркетологи компании "std::steak" разработали новый рекламный проект "Стейк или кипячение". Суть проекта заключается в захвате рынка всей Берляндии. Группы агентов будут заходить в каждый дом каждого города и задавать глупый вопрос: "Стейк или кипячение?". Таким образом компания расчитывает полностью повергнуть в ужас всех конкурентов и озадачить потенциальных покупателей.
Высадка групп агентов произойдёт в некоторых городах Берляндии с воздуха. Далее по дорогам агенты должны посетить все города страны. Города соединены односторонними дорогами, для каждой дороги задана её длина. В каждом городе группы могут делится произвольным образом (количество человек в группе изначально чрезвычайно велико).
Известно, что затраты на перемещение по дороге равны её длине. Для каждого города известна стоимость организации высадки десанта в него.
Какой наименьший бюджет может иметь операция "Стейк или кипячение"?
Входные данные
Входной файл состоит из одного или нескольких наборов входных данных.
В первой строке каждого набора записана пара целых чисел N, M (1 ≤ N ≤ 300, 0 ≤ M ≤ N^2-N), где N - количество городов в Берляндии, а M - количество дорог. Во второй строке записана последовательность A_1, A_2, ..., A_N, где A_i- стоимость высадки десанта в пукт i (1 ≤ A_i ≤ 1000). Далее в M строках описаны дороги тройками чисел X_i, Y_i, L_i, где X_i - стартовый город дороги, Y_i - конечный, а L_i - её длина (1 ≤ X_i, Y_i ≤ N, X_i ≠ Y_i, 1 ≤ L_i ≤ 1000). Между каждой парой городов существует не более одной дороги в каждом направлении.
Сумма значений N по всем наборам входных данных не превосходит 300.
Выходные данные
Для каждого набора входных данных выведите искомый наименьший бюджет.