eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дороги в Байтляндії

Дороги в Байтляндії

\includegraphics{https://static.e-olymp.com/content/ba/ba1df58a183588239a1319b6ec8ce11407865dee.jpg} Країна Байтляндія розташована на островах. Пройшли вибори нового президента і перегони виграв Бітик. На своєму новому \textit{RoverLand}i президент захотів відвідати острови. Для цього йому потрібно побудувати мости між деякими островами так, щоб від столиці було сполучення з будь-яким іншим островом. Оскільки бюджет будівництва в країні обмежений, то мости треба будувати одно направленими. Після того як Бітик відвідав деякий острів, за ним присилають вертоліт, який забирає його та його транспортний засіб в столицю (бюджет на польоти не обмежений, але проїхати через новопобудовані мости це обов’язок президента Байтляндії). Тобто маршрут народного президента складається з двох частин: \begin{enumerate} \item на \textit{RoverLand}i він добирається на деякий острів; \item з острова в столицю президент вертається на вертольоті. \end{enumerate} За кожний кілометр моста потрібно заплатити \textbf{1} Байтляндський тугрик. Президентові архітектори надали список мостів, які теоретично можна побудувати, не пошкодивши природу островів. Допоможіть Бітику порахувати який мінімальний бюджет потрібно виділити на побудову мостів, так щоб зі столиці можна було добратися на інші острова на \textit{RoverLand}i. \InputFile У першому рядку знаходиться два числа \textbf{N} (\textbf{1} ≤ \textbf{N} ≤ \textbf{10^4}) -- число островів, та \textbf{M} (\textbf{1} ≤ \textbf{M} ≤ \textbf{10^5}) -- кількість проектів для мостів. У наступних \textbf{M} рядках по \textbf{3} натуральних числа: \textbf{u} (\textbf{1} ≤ \textbf{u} ≤ \textbf{N}), \textbf{v} (\textbf{1} ≤ \textbf{v} ≤ \textbf{N}), \textbf{w} (\textbf{1} ≤ \textbf{w} ≤ \textbf{10^5}), де \textbf{u}, \textbf{v} -- номери островів, які з’єднує міст, що запропонований у даному проекті, та \textbf{w} -- його довжина. Між двома островами може бути декілька проектів мостів, з різними довжинами, а також не існує моста, який не веде на інший острів. У останньому рядку одне натуральне число \textbf{X} (\textbf{1} ≤ \textbf{X} ≤ \textbf{N}) -- номер острова, на якому розміщена столиця країни. \OutputFile Якщо існує острів, на який Бітик ніяк не зможе доїхати на RoverLandi, вивести слово "\textbf{Helikopter}" (без лапок), інакше вивести вартість усіх робіт.
Ліміт часу 0.5 секунд
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
5 5
1 2 4
1 5 5
2 3 3
3 4 2
4 2 1
1
Вихідні дані #1
14
Автор Остап Столярчук
Джерело Дистанційна Літня Комп`ютерна Школа - літо 2013 року