Новый русский Колян уверен, что проводить время в дорожных пробках ниже его достоинства. Вот почему он поставил мигалку на крышу своего Хаммера и не имел проблем до последнего решения городской администрации. Теперь каждая улица города принадлежит одной или нескольким категориям, и водитель должен иметь отдельные разрешения, чтобы использовать мигалку на улицах каждой категории. Если улица принадлежит нескольким категориям, достаточно иметь разрешение на хотя бы одну из этих категорий. Для каждой категории разрешение выдаётся отдельным городским чиновником. При этом все они за выдачу разрешений берут взятки одинакового размера. Помогите Коляну найти путь от дома до работы, который он может проехать с включённой мигалкой, при этом потратив минимальное количество денег на взятки.

Ввод содержит план улиц в следующем формате. В первой строке находятся целые числа K, N и M, где K — количество категорий улиц (1 ≤ K ≤ 20), N — число перекрёстков (2 ≤ N ≤ 30), а M — число описаний отрезков улиц между перекрёстками.

Каждая из следующих M строк описывает отрезок улицы тремя целыми числами V₁ V₂ C, где V₁ и V₂ — номера перекрёстков, ограничивающих этот отрезок дороги, а C — его категория. Перекрёстки занумерованы от 0 до N – 1, категории занумерованы от 0 до K – 1. Для любой пары перекрестков не существует двух дорог одной и той же категории, связывающих эти перекрестки.

Выведите в первой строке минимальное число разрешений, необходимых для проезда от перекрёстка 0 (дом Коляна) до перекрёстка 1 (работа Коляна) со включённой мигалкой.

Во второй строке выведите список категорий, на которые нужно получить разрешения. Числа должны быть разделены пробелами. Гарантируется, что такой список всегда существует.