{"trustable":false,"sections":[{"title":"","value":{"format":"MD","content":"Есть n SMTP-серверов, соединенных сетевыми кабелями. Каждый из m кабелей соединяет два компьютера и имеет определенную задержку, измеряемую в миллисекундах, необходимую для отправки сообщения электронной почты. Какие\nсамое короткое время, необходимое для отправки сообщения с сервера S на сервер T по последовательности кабелей?\nПредположим, что ни на одном из серверов нет задержек.\n\n#### Входные данные\n\nВ первой строке вводится Q -- количество тестов, за которыми следует Q тестов. Каждый начинается со строки\nсодержащий n (2 ≤ n ≤ 20000), m (0 ≤ m ≤ 50000), S (0 ≤ S \u003c n) и T (0 ≤ T \u003c n). S !\u003d T.\nследующие m строк будут содержать 3 целых числа: 2 разных сервера (в диапазоне [0, n - 1]), которые подключены\nдвунаправленным кабелем и задержкой w вдоль этого кабеля (0 ≤ w ≤ 10000).\n\n#### Выходные данные\n\nДля каждого теста выведите строку «Case #x:» и количество миллисекунд, необходимых для отправки.\nсообщение от S до T. Выведите unreachable, если нет маршрута от S до T.\n\n#### Пример ввода\n\n3\n2 1 0 1\n0 1 100\n3 3 2 0\n0 1 100\n0 2 200\n1 2 50\n2 0 0 1\n\n#### Пример вывода\n\nCase #1: 100\nCase #2: 150\nCase #3: unreachable\n\n\n"}}]}