Догонялки на островах
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Моана пытается догнать Мауи, который отправился в отпуск по островам за рифом, чтобы забрать у него Сердце Те Фити.

За рифом находятся $$$n$$$ островов, между которыми можно перемещаться, используя двусторонние паромы местных туземцев с развитой инфраструктурой. Есть ровно $$$m$$$ маршрутов, $$$i$$$-й используется для поездки c острова $$$v_i$$$ на остров $$$u_i$$$ (и из $$$u_i$$$ в $$$v_i$$$) и стоит $$$w_i$$$ тугриков.

Моана знает, что Мауи собирается посетить все острова и расширить свой кругозор. Также Моана знает, что вождь каждого острова берет налог на его посещение (развитая инфраструктура требует тугриков). Налог посещения $$$i$$$-го острова составит $$$a_i$$$ тугриков.

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

Формально, для каждого $$$u \in [1, n]$$$ требуется посчитать $$$\min\limits_{v=1}^n 2 \mathtt{dist}(u, v) + a_v$$$, где $$$\mathtt{dist}(u, v)$$$ — минимальное количество тугриков, нужных для поездки с острова $$$u$$$ на остров $$$v$$$.

Входные данные

В первой строке записано два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$).

Затем идет $$$m$$$ строк, в $$$i$$$-й записаны три целых числа $$$v_i$$$, $$$u_i$$$ и $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \ne u_i$$$; $$$1 \le w_i \le 10^9$$$), определяющие $$$i$$$-й маршрут парома. Между каждой парой островов существует не больше одного паромного маршрута, то есть, для каждой пары $$$(v, u)$$$ во входных данных нет ни $$$(u, v)$$$, ни дополнительных вхождений $$$(v, u)$$$.

В следующей строке записаны $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ..., $$$a_k$$$ ($$$1 \le a_i \le 10^{12}$$$) —– налог на посещение острова $$$i$$$.

Выходные данные

Выведите $$$n$$$ целых чисел. $$$i$$$-е из них должно быть равно минимальному количеству тугриков, которое придется потратить Моане для того, чтобы с острова $$$i$$$ добраться до какого-либо острова $$$j$$$ (или остаться на острове $$$i$$$), заплатить налог на посещение острова и забрать сердце Те Фити, и вернуться на остров $$$i$$$ (если $$$j \ne i$$$).

Примеры

Входные данные
4 2
15 3 10 2
2 3 2
3 4 3
Выходные данные
15 3 7 2 
Входные данные
3 3
10 20 30
1 2 1
1 3 1
2 3 1
Выходные данные
10 12 12