Neft kəmərləri#4391
Oliqarx Vovan, digər oliqarxlar kimi, Qərbi Kukulandiyadan Şərqi Kukulandiya neftini nəql etməklə məşğuldur. Onun Qərbi Kukulandiyada böyük bir neft çıxarma stansiyası, Şərqi Kukulandiyada isə böyük bir neft emalı stansiyası, həmçinin neftin bu iki bölgə arasında ötürülməsi üçün boru kəmərləri şəbəkəsi var. Vovanın masasının üstündə bu boru kəmərlərinin xəritəsi var və maraqlıdır, bu sistemin neçə vahid neft ötürə biləcəyini müəyyən etmək.
Hər bir boru kəməri müəyyən iki stansiyanı birləşdirir. Xəritədə bütün stansiyalar nömrələnib: çıxarma stansiyası nömrəsini, emal stansiyası isə nömrəsini daşıyır, tranzit stansiyalar -dən N-1-ə qədər nömrələnir. Hər bir boru kəmərinin müəyyən tutumu var, lakin bu kəmərdən neft hər iki istiqamətə axa bilər. Vovan bilmir ki, Yer yuvarlaqdır, ona görə də onun xəritəsində hər bir stansiyanın düz koordinatları var (x_i və y_i — -ci stansiyanın koordinatları). Boru kəmərləri isə düz xətt seqmentləri ilə göstərilib. Xəritədə borular yalnız ümumi stansiyada (zirvədə) kəsişə bilər. Məlumdur ki, bütün stansiyalar arasında çıxarma stansiyasının koordinatı ən kiçikdir, emal stansiyasının isə koordinatı ən böyükdür.
Birinci sətirdə xəritədəki stansiyaların sayı verilir (2 \leq N \leq 10000). Növbəti sətirdə stansiyaların koordinatları gəlir (x_i, y_i) — arada boşluqla ayrılmışdır. Koordinatlar 10^8-dən böyük olmamaq şərtilə tam ədəddir. Sonrakı sətirdə — boru kəmərlərinin sayı verilir. Daha sonra isə növbəti sətirdə hər bir boru kəməri təsvir olunur: boru ilə birləşdirilən iki stansiyanın nömrələri və boru kəmərinin ötürmə qabiliyyəti — -dən 10^8-ə kimi tam ədəd. Zəmanət verilir ki, boru kəməri sistemi sıfırdan fərqli miqdarda neft ötürə bilər, lakin 2 \cdot 10^9 vahiddən çox ötürə bilməz.
Birinci sətirdə Vovanın sisteminin nəql edə biləcəyi maksimum neft vahidinin sayını yazın. Sonrakı sətirdə nəql planını verin — (, , ) üçlüyü, burada vahid neftin stansiyasından stansiyasına axdığı göstərilir. Hər bir boru kəməri bu siyahıda dəqiq bir dəfə olmalıdır (neft axın olmayan borular da daxil). Bütün üçlüklərdə qeyri-mənfi olmalıdır.
Nümunə 1