В эфире величайшее интеллектуальное шоу современности — «Кто хочет стать немалоньером?»! И сегодня у нас в гостях, под звуки величественной барабанной дроби, Горилл!
Правила нашего грандиозного шоу таковы: наш бессменный архитектор Кобб получает безграничные ресурсы для создания лабиринта и подготовки уникальной задачи, которую наш гость должен будет решить.
Поистине величественный лабиринт уже возведён, и он представляет собой $$$n$$$ зал ослепительной красоты, пронумерованных от $$$1$$$ до $$$n$$$. Залы соединены между собой $$$m$$$ тоннелями, причём $$$i$$$-й тоннель соединяет залы с номерами $$$u_i$$$ и $$$v_i$$$ и имеет длину $$$w_i$$$ (по нему можно пройти как из залы $$$u_i$$$ в залу $$$v_i$$$, так и из залы $$$v_i$$$ в залу $$$u_i$$$). Кобб гарантирует, что между двумя залами может быть проведено не более одного тоннеля.
Сегодняшний гость — истинный интеллектуал, и поэтому задача, которую мы для него подготовили, будет особенной: Горилла поместят в $$$1$$$-ю залу, и он должен будет отыскать кратчайший путь от неё до каждой залы этого загадочного лабиринта!
Но мы не были бы величайшим шоу на планете, если бы всё было так просто! Архитектор предоставит нашему гостю загадочные числа $$$c_1, c_2, \cdots, c_n$$$. В его распоряжении будет уникальная подсказка — «телепортация», которая дарует ему возможность, находясь в зале с номером $$$a$$$, создать тоннель длиной $$$c_a$$$ до любой залы, до которой ещё нет тоннеля из нашей залы. Однако эту могущественную подсказку можно использовать лишь единожды! Заметим, что кратчайшее расстояние для всех зал считается независимо, то есть подсказку можно применить не более одного раза в каждом отдельном подсчёте ответа для зал.
В первой строке задано единственное число $$$t$$$ ($$$1 \leq t \leq 10000$$$) — количество наборов входных данных. Затем следует их описание.
В первой строке каждого набора входных данных заданы $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) и $$$m$$$ ($$$0 \leq m \leq 2 \cdot 10^5$$$) — количество зал и тоннелей в графе.
Во второй строке каждого набора входных данных заданы таинственные числа $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \leq c_i \leq 10^9$$$).
В следующих $$$m$$$ строках идёт описание тоннелей.
Каждый тоннель задан в отдельной строке числами $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) и $$$w_i$$$ ($$$0 \leq w_i \leq 10^9$$$) — означающие тоннель между вершинами $$$u_i, v_i$$$ длины $$$w_i$$$.
Гарантируется, что каждый тест задает корректный лабиринт — граф без петель и кратных рёбер, и что сумма $$$n$$$ и $$$m$$$ по отдельности по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите $$$n$$$ чисел — кратчайшие пути до всех зал.
36 4100 4 3 2 1 1001 2 12 3 22 6 1004 6 12 01000000000 01 01000000000
0 1 3 5 5 6 0 1000000000 0
В примере в первом наборе тестовых данных:
$$$1$$$: мы и так находимся в зале $$$1$$$, кратчайший путь длины $$$0$$$;
$$$1 \rightarrow 2$$$: кратчайший путь длины $$$1$$$;
$$$1 \rightarrow 2 \rightarrow 3$$$: кратчайший путь длины $$$1 + 2 = 3$$$;
$$$1 \rightarrow 2 \rightarrow 4$$$: с помощью подсказки построили тоннель из $$$2$$$ в $$$4$$$ длины $$$c_2 = 4$$$, кратчайший путь длины $$$1 + 4 = 5$$$
$$$1 \rightarrow 2 \rightarrow 5$$$: с помощью подсказки построили тоннель из $$$2$$$ в $$$5$$$ длины $$$c_2 = 4$$$, кратчайший путь длины $$$1 + 4 = 5$$$;
$$$1 \rightarrow 2 \rightarrow 4 \rightarrow 6$$$: с помощью подсказки построили тоннель из $$$2$$$ в $$$4$$$ длины $$$c_2 = 4$$$, кратчайший путь длины $$$1 + 4 + 1 = 6$$$.
