Посвята
Щоб стати дорослим гномом, потрібно пройти страшний-страшний лабіринт. Лабіринт настільки заплутаний та небезпечний, что гномиків у нього потрібно пускати парами. Звичайно ж, пара повинна складатись з хлопчика та дівчинки. Оскільки буває різна кількість хлопчиків та дівчаток, комусь доведеться проходити лабіринт декілька разів (головне, щоб гномик пройшов його хоча б раз).
Для кожної пари хлопчик-дівчинка, які дружать між собою, дорослі гномы знають час, за який ця парочка знайде вихід з лабіринту. Допоможіть їм провести усіх дітей через лабіринт за мінимально можливий час.
Вхідні дані
Перший рядок вхідного файлу містить два цілих числа n та m - кількість хлопчиків та дівчаток у гномиків відповідно (1 ≤ n, m ≤ 100), другий рядок містить число r - кількість пар, яких можна пускати разом (1 ≤ r ≤ 1000). Наступні r рядків містять по три числа кожен: a_i, b_i та c_i. Ці числа означають, що хлопчик з номером a_i може піти у лабіринт з дівчинкою з номером b_i, і вони пробудуть там разом c_i секунд (1 ≤ c_i ≤ 1000). Гарантується, що у кожного гномика є друг (подруга), з яким(ою) вона(він) може піти у лабіринт.
Вихідні дані
У першому рядку вихідного файлу виведіть мінімальний час, за який можна провести посвяту. У другому рядку виведіть k - кількість пар, які потрібно пустити у лабіринт. Третій рядок повинен міститиь k цілих чисел - номери цих пар, як вони задані у вхідному файлі.