Регата стартовала, и кругосветная гонка в самом разгаре. Экипаж <<Беды>>, состоящий из капитана Врунгеля, студента Лома и шулера Фукса, настроен на победу. В зоне видимости экипажа находятся $n$ островов. Из-за розы ветров и подводных течений количество фарватеров (прямых маршрутов между островами) ограничено. Капитан обнаружил $m$ направленных фарватеров, $j$-й фарватер позволяет добраться с острова $v_j$ на остров $u_j$ и имеет длину $w_j$.

Некоторые фарватеры находятся в зоне \textit{мёртвого штиля}. После \textbf{каждого} перемещения <<Беды>> направление такого фарватера меняется на противоположное. Например, если фарватер $2 \to 4$ длины $1$ находится в зоне \textit{мёртвого штиля}, после первого перемещения <<Беды>> по любому фарватеру он превратится в фарватер $4 \to 2$ длины $1$, после второго~--- в фарватер $2 \to 4$ длины $1$, и так далее.

Останавливаться на островах необходимо для пополнения запасов. Помогите капитану Врунгелю найти кратчайшее расстояние от острова $1$ до всех остальных. Расстояние считается как сумма длин пройденных фарватеров.

\begin{center}
\includegraphics{pic3.png}
\end{center}
