Нафтопроводи#4391
Олігарх Вован, як і багато інших олігархів, займається транспортуванням нафти із Західної Кукуляндії до Східної Кукуляндії. Він володіє великою нафтовидобувною станцією в Західній Кукуляндії, такою ж великою нафтопереробною станцією у Східній Кукуляндії та мережею нафтопроводів, що передають нафту між цими двома регіонами. На столі Вована лежить карта цих нафтопроводів, і було б цікаво дізнатися, скільки одиниць нафти може транспортувати ця система.
Кожен нафтопровід з'єднує конкретну пару станцій. На карті всі станції пронумеровано: видобувна станція має номер , переробна станція — номер , а транзитні станції мають номери від до N - 1. Кожен нафтопровід має обмежену пропускну здатність для транспортування нафти, проте він може переносити нафту в будь-якому напрямку. Вован не знає, що Земля кругла, тому кожна станція на його карті має плоскі координати (x_i, y_i — координати -ої станції). Нафтопроводи зображено у вигляді відрізків прямих. На карті нафтопроводи можуть перетинатися лише у спільній станції (вершині). Відомо, що серед усіх станцій видобувна станція має найменшу -координату, а переробна — найбільшу -координату.
У першому рядку задано число — кількість станцій на карті (2 \leq N \leq 10000). У наступних рядках наведені координати станцій (x_i, y_i) через пробіл. Координати — цілі числа за модулем не більше 10^8. Наступний рядок містить ціле число — кількість нафтопроводів. Далі у наступних рядках містяться описи нафтопроводів: пара номерів станцій, які з'єднує нафтопровід, і потужність нафтопроводу в одиницях — ціле число від до 10^8. Гарантовано, що система нафтопроводів може транспортувати ненульову кількість нафти, але не більше ніж 2 \cdot 10^9 одиниць нафти.
У першому рядку виведіть максимальну кількість одиниць нафти, яку система Вована може транспортувати. У наступних рядках подайте план транспортування — трійки чисел (, , ), що означають, що одиниць нафти мають йти зі станції до станції . Кожен нафтопровід повинен бути присутній у цьому списку рівно один раз (навіть якщо через нього не йде нафта). Значення у всіх трійках повинні бути невід’ємними.
Приклад 1