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