ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1664. Нефтепроводы

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Олигарх Вован, как и большинство других олигархов, занимается транспортировкой нефти из Западной Кукуляндии в Восточную Кукуляндию. В его владении находится огромная нефтедобывающая станция в Западной Кукуляндии, не меньшего размера нефтеперерабатывающая станция в Восточной Кукуляндии, а также система нефтепроводов, по которым нефть перегоняется из одной страны в другую. На столе у Вована лежит карта нефтепроводов. Хотелось бы знать, какое количество условных единиц нефти может транспортировать данная система.
Каждый нефтепровод соединяет некоторую пару станций. На карте все станции пронумерованы, при этом добывающая станция имеет номер 1, перерабатывающая — номер N, а транзитные — номера от 2 до N − 1. Каждый нефтепровод может транспортировать ограниченное количество нефти, зато в любом направлении. Вован не знает, что Земля круглая, поэтому каждая станция на его карте имеет плоские координаты (xi и yi — координаты i-й станции). Нефтепроводы являются отрезками прямых. На карте пара нефтепроводов может пересекаться только по общей станции-вершине. Известно, что среди всех станций добывающая станция имеет наименьшую координату x, а перерабатывающая — наибольшую координату x.

Исходные данные

В первой строке дано целое число N — количество станций на карте (2 ≤ N ≤ 10000). В следующих N строках перечислены координаты станций (xiyi) через пробел. Координаты — целые числа, по модулю не превосходящие 108. В следующей строке дано целое число M — количество нефтепроводов. Далее в M строках через пробел перечислены характеристики нефтепроводов — пара номеров станций, соединяемых нефтепроводом, а также пропускная способность нефтепровода в условных единицах — целое число от 1 до 108. Гарантируется, что система нефтепроводов может траспортировать некоторое ненулевое количество нефти, но не может транспортировать более 2·109 условных единиц нефти.

Результат

В первой строке выведите наибольшее количество условных единиц нефти, которое может транспортировать система Вована. В следующих M строках выведите план транспортировки — тройки чисел (ABC), означающие, что из станции A в станцию B должно течь C условных единиц нефти. Все нефтепроводы должны быть представлены в данном списке ровно один раз (даже те, по которым ничего не течёт). Число C во всех тройках должно быть неотрицательным.

Пример

исходные данныерезультат
3
0 0
1 1
2 0
2
1 2 2
2 3 1
1
1 2 1
2 3 1
Автор задачи: Артём Мелентьев
Источник задачи: Ural SU Contest. Petrozavodsk Winter Session, January 2008