Участники популярной музыкальной группы «Flayer» объявили о своем прощальном мировом турне. Разумеется, посетят они и Берляндию.
В Берляндии n городов. Между городами можно перемещаться, используя двусторонние железнодорожные маршруты; есть ровно m маршрутов, i-й используется для поездки из города vi в город ui (и из ui в vi) и стоит wi монет.
«Flayer» посетят все города, в i-м городе цена билета на концерт составит ai монет.
У вас есть друзья в каждом городе Берляндии, и все знают о ваших программистских способностях! Они просят вас посчитать, за какое минимальное количество монет им удастся посетить концерт. Для каждого города i необходимо посчитать минимальное количество монет, которое придется потратить жителю города i, чтобы доехать до какого-либо города j (или остаться в городе i), посетить там концерт, и вернуться в город i (если j ≠ i).
Формально, для каждого 
требуется посчитать 
, где d(i, j) — минимальное количество монет, нужных для поездки из города i в город j. Если невозможно приехать в город j из города i, то d(i, j) считается бесконечно большим.
Выходные данные
Выведите n целых чисел. i-е из них должно быть равно минимальному количеству монет, которое придется потратить жителю города i для того, чтобы доехать до какого-либо города j (или остаться в городе i), посетить там концерт, и вернуться в город i (если j ≠ i).