Рабочее место участника

В Стране Дураков `N` городов, соединенных сетью из `M` автомобильных дорог. Движение по всем дорогам двустороннее и из любого города можно попасть в любой другой. Столица страны имеет номер 1. Каждая дорога в стране имеет некоторую целую неотрицательную длину.

В очередном своем ежегодном отчете Министерство Образования и Транспорта представило данные о длинах кратчайших путей из столицы страны до всех остальных городов. Поскольку эти данные готовились впопыхах, то большинство из них оказалось взято "с потолка". Для того, чтобы данные казались более правдоподобными, все объявленые расстояния были различными. К сожалению, Счетная Палата пожелала проверить деятельность Министерства и, в частности, истинность данных.

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

Поскольку удлинение существующих дорог (а тем более уменьшение их длины!) занятие дорогостоящее, то министр вынужден искать такой план, при котором суммарное изменение всех длин было бы минимально. Конечно, никакие старания министра и дорожных служб не в силах сделать длину дороги отрицательной.

В первой строке входного файла находятся числа `N` и `M` (`1\ ≤\ N\ ≤\ 4\ 000`, `1\ ≤\ M\ ≤\ 100\ 000`). Следующая строка содержит `N` различных целых чисел `D_i`, не превосходящих по модулю `100\ 000`, — опубликованные расстояния от столицы до городов. Следующие `M` строк содержат описание существующих дорог — города, которые соединяет дорога, и ее длина (длина дороги задается неотрицательным целым числом, не превышающим `10\ 000`).

Если изменить длины дорог указанным способом невозможно, выведите на первой строке выходного файла число `-1`. В противном случае выведите минимальное возможное суммарное изменение длины дорог. На следующих `M` строках выведите новые длины дорог.

4 5
0 2 3 4
1 2 1
1 3 3
2 4 3
1 4 3
4 3 1

2
2
3
3
4
1

4 4
0 2 3 1
1 2 1
1 3 1
2 4 1
3 4 1

-1