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