eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

\includegraphics{https://static.e-olymp.com/content/ba/ba1df58a183588239a1319b6ec8ce11407865dee.jpg} Страна Байтляндия расположена на островах. Прошли выборы нового президента и избирательную кампанию выиграл Битик. На своём новом \textit{RoverLand}е президент захотел посетить острова. Для этого ему нужно построить мосты между некоторыми островами так, чтобы от столицы было сообщение с любым другим островом. так как бюджет строительства в стране ограничен, то мосты нужно строить однонаправленными. После того как Битик посетил некоторый острів, за ним присилают вертолёт, который забирает его самого и его транспортное средство в столицу (бюджет на полёты не ограничен, но проехать по вновь построенным мостам - это обязанность президента Байтляндии). То есть маршрут народного президента состоит из двух частей: \begin{enumerate} \item на \textit{RoverLand}е он добирается на некоторый остров; \item с острова в столицу президент возвращается на вертолёте. \end{enumerate} За каждый километр моста нужно заплатить \textbf{1} Байтляндький тугрик. Президентские архитекторы предоставили список мостов, которые теоретичски можно построить, не повредив природу островов. Помогите Битику посчитать какой минимальный бюджет нужно выделить на построение мостов, так чтобы со столицы можна было добраться на другие острова на \textit{RoverLand}е. \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 Если существует остров, на который Битик никак не сможет доехать на \textit{RoverLand}е, вывести слово "\textbf{Helikopter}" (без кавычек), иначе вывести стоимость всех работ.
Zaman məhdudiyyəti 0.5 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
5 5
1 2 4
1 5 5
2 3 3
3 4 2
4 2 1
1
Çıxış verilənləri #1
14
Müəllif Остап Столярчук
Mənbə Дистанционная Летняя Компьютерная Школа - лето 2013 года