Олигарх Вован, как и большинство других олигархов, занимается транспортировкой нефти из Западной Кукуляндии в Восточную Кукуляндию. В его владении находится огромная нефтедобывающая станция в Западной Кукуляндии, не меньшего размера нефтеперерабатывающая станция в Восточной Кукуляндии, а также система нефтепроводов, по которым нефть перегоняется из одной страны в другую. На столе у Вована лежит карта нефтепроводов. Хотелось бы знать, какое количество условных единиц нефти может транспортировать данная система.

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

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

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