У казковій країні, столицею якої є Смарагдове Місто, всього \(N\) міст. Деякі міста з'єднані дорогою, повністю вимощеною жовтою цеглою. Еллі потрібно дістатися з міста на кордоні до Смарагдового Міста і потім повернутися назад. Щоб не було нудно, їй хочеться добиратися туди і назад різним маршрутом (а саме так, щоб жодна з доріг не була і маршруті туди і на маршруті назад ). Оскільки дарма витрачати час вона не збирається, то для кожного шляху хоче вибрати найкоротший варіант.

Напишіть програму, яка допоможе Еллі визначити, чи можлива така подорож, і якщо вона можлива, то розробить для неї маршрут.

Всі міста пронумеровані натуральними числами від 1 до \(N\), місто на кордоні має номер \(K\), Смарагдовий Місто має номер \(N\).

Формат вхідних даних

У першому рядку містяться три числа: \(N\), \(K\) і \(M\) (\(1 ≤ N ≤ 100\), \(1 ≤ K < N\), \(0 \le M \le N(N-1)/2\) ), де ), де \(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