Моана пытается догнать Мауи, который отправился в отпуск по островам за рифом, чтобы забрать у него Сердце Те Фити.
За рифом находятся $$$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 215 3 10 22 3 23 4 3
15 3 7 2
3 310 20 301 2 11 3 12 3 1
10 12 12