Олігарх Вован, як і більшість інших олігархів, займається транспортуванням нафти з Західної Кукуляндії у Східну Кукуляндію. В його володіннні знаходиться величезна нафтодобуваюча станція у Західній Кукуляндії, не меншого розміру нефтопереробна станція у Східній Кукуляндії, а також система нафтопроводів, по яким нафта перегоняється з однієї країни в іншу. На столі у Вована лежить карта нафтопроводів. Хотілось би знати, яку кількість умовних одиниць нафти може транспортувати дана система. Кожен нафтопровід з'єднує деяку пару станцій. На карті усі станції пронумеровані, при цьому добуваюча станція має номер \textbf{1}, переробна - номер \textbf{N}, а транзитні - номери від \textbf{2} до \textbf{N-1}. Кожен нафтопровід може транспортувати обмежену кількість нафти, проте у довільному напрямку. Вован не знає, що Земля кругла, тому кожна станція на його карті має плоскі координати (\textbf{x_i} та \textbf{y_i} - координати \textbf{i}-ї станції). Нафтопроводи є відрізками прямих. На карті пара нафтопроводів може перетинатись лише у спільній станції-вершині. Відомо, що серед усіх станцій добуваюча станція має найменшу координату \textbf{x}, а переробна- найбільшу координату \textbf{x}. \InputFile У першому рядку задано число \textbf{N} - кількість станцій на карті (\textbf{2} ≤ \textbf{N} ≤ \textbf{10000}). У наступних \textbf{N} рядках перераховано координати станцій (\textbf{x_i}, \textbf{y_i}) через пропуск. Координати - цілі числа, які по модулю не перевищують \textbf{10^8}. У наступному рядку задано ціле число \textbf{M} - кількість нафтопроводів. Далі у \textbf{M} рядках через пропуск перераховані характеристики нафтопроводів - пара номерів станцій, з'єднаних нафтопроводом, а також пропускна здатність нафтопровода в умовних одиницях - ціле число від \textbf{1} до \textbf{10^8}. Гарантується, що система нафтопроводів може транспортувати деяку ненульову кількість нафти, але не може транспортувати більше \textbf{2·10^9} умовних одиниць нафти. \OutputFile У першому рядку виведіть найбільшу кількість умовних одиниць нафти, які може транспортувати система Вована. У наступних \textbf{M} рядках виведіть план транспортування - трійки чисел (\textbf{A}, \textbf{B}, \textbf{C}), які означають, що зі станції \textbf{A} у станцію \textbf{B} повинно текти \textbf{C} умовних одиниць нафти. Усі нафтопроводи повинні бути представлені у даному списку рівно один раз (навіть ті, по яким нічого не тече). Число \textbf{C} в усіх трійках повинно бути невід'ємним.