На цей раз, щоб стати ЛКШатом, потрібно пройти страшний-страшний лабіринт. Лабіринт настільки заплутаний та небезпечний, що школярів у нього треба пускати парами. Звичайно ж, пара повинна складатися з хлопчика та дівчинки. Оскільки в ЛКШ різна кількість хлопчиків і дівчаток, комусь доведеться проходити лабіринт кілька разів (головне, щоб школяр пройшов його хоча б раз).

Для кожної пари хлопчик-дівчинка, які дружать між собою, культорги знають час, за який ця парочка знайде вихід із лабіринту. Допоможіть їм провести всіх дітей через лабіринт за мінімально можливий час.

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

Перший рядок вхідного файлу містить два цілих числа \(n\) і \(m\) - кількість хлопчиків і дівчаток у ЛКШ відповідно (\(1 \le n, m \le 100\)).

Другий рядок містить число \(r\) - кількість пар, яких можна пускати разом (\(1 \le r \le 1000\)).

Наступні \(r\) рядків містять по три числа кожна: \(a_i\), \(b_i\) та \(c_i\). Ці числа означають, що хлопчик з номером \(a_i\) може піти до лабіринту з дівчинкою з номером \(b_i\), і вони пробудуть там разом \(c_i\) секунд (\(1 \le c_i \le 1000\)).

Гарантується, що у кожного школяра є друг/подруга, з яким вона/він може піти в лабіринт.

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

У першому рядку вихідного файлу виведіть мінімальний час, за який можна провести посвяту.

У другому рядку виведіть \(k\) - кількість пар, які слід пустити у лабіринт.

Третій рядок повинен містити \(k\) цілих чисел - номери цих пар, як вони дано у вхідному файлі.

Приклад вхідних даних

3 3
7
1 1 3
1 2 2
1 3 4
2 1 3
2 2 9
3 1 2
3 3 11

Приклад вихідних даних

11
4
2 3 4 6