Задача №111527. Туда и обратно
В сказочной стране, столицей которой является Изумрудный Город, всего N городов. Некоторые города соединены дорогой, целиком вымощеной желтым кирпичем. Элли нужно добраться из города на границе в Изумрудный Город и затем вернуться обратно. Чтобы не было скучно, ей хочется добираться туда и обратно разным маршрутом (а именно так, чтобы ни одна из дорог не была и на маршруте туда и на маршруте обратно). Поскольку зря тратить время она не собирается, то для каждого пути она хочет выбрать самый короткий вариант.
Напишите программу, которая поможет Элли определить, возможно ли такое путешествие, и если оно возможно, то разработает для нее маршрут.
Все города пронумерованы натуральными числами от 1 до N, город на границе имеет номер K, Изумрудный Город имеет номер N.
В первой строке содержатся три числа: N, K и M (1 ≤ N ≤ 100, 1 ≤ K < N, 
), где N -– количество городов в Сказочной стране, K – номер города, из которого Элли начинает путешествие, M – количество дорог, мощеных желтым кирпичем. В следующих M строках вводятся по три числа – номера городов, соединенных дорогой из желтого кирпича и длина этой дороги.
В первой строке выведите -1, если желание Элли неосуществимо. В противном случае в первой строке выведите два числа: длину пути туда и длину пути обратно, а в следующих двух строках: номера городов на пути туда и на пути обратно в том порядке, в котором она будет их проходить.
4 1 6
1 4 3
2 4 2
2 3 1
1 2 5
1 3 6
4 3 8
3 7
1 4
4 2 1
4 1 0
-1