Маркетологи компанії "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 Для кожного набору вхідних даних виведіть шуканий найменший бюджет.