Qara gavalı#2482
Drenaj sistemi müstəvidə yerləşən və drenaj qovşaqlarını birləşdirən drenaj xətlərindən (seqmentlərdən) ibarətdir. Bu xətlər yalnız onların uclarında — drenaj qovşaqlarında kəsişirlər. Hər bir xətin tutumu (həcmi) var, yəni onun vasitəsilə vahid zamanda neçə vahid maye axa biləcəyini göstərir. Müstəvidə xüsusi drenaj çıxışı olan bir drenaj qovşağı — mövcuddur. Maye bir xətdən istənilən istiqamətdə axa bilər, lakin eyni anda yalnız bir istiqamətdə axa bilər.
Drenaj xətləri müstəvini bir neçə sahəyə bölür, bu sahələrə iş sahələri deyilir (xarici sahə də iş sahəsi hesab olunur). Vasya hazırda bu sahələrdən birindədir və həmin sahənin sərhədində ümumi drenaj çıxışı yerləşir. Lakin texniki məhdudiyyətlərə görə, o, çıxışdan birbaşa istifadə edə bilmir. Vasya tezliklə kərə yağını drenaj xətləri vasitəsilə qovşaqlardan axıdıb çıxışına çatdırmalıdır. Bunun üçün Vasya kərə yağını xüsusi bir qovşağa — -ə axıtmağı planlaşdırır. Qəbul edilir ki, kərə yağı dərhal yayılır və heç bir drenaj xəttindən onun tutumundan artıq vahid yağ axa bilməz. Tapşırığınız Vasya'nın vahid zamanda axıda biləcəyi maksimum kərə yağı miqdarını müəyyən etməkdir.
Girişin ilk sətrində drenaj qovşaqlarının sayı , drenaj xətlərinin sayı , Vasya'nın istifadə edəcəyi qovşaq və ümumi çıxış qovşağı (1 \leq n \leq 50000, 1 \leq m \leq 3n, 1 \leq s, t \leq n, s \neq t) verilir. Sonra gələn sətirdə drenaj qovşaqlarının koordinatları — tam ədədlər olan x_i y_i (|x_i|, |y_i| \leq 10^9) göstərilir. Heç iki drenaj qovşağı bir yerdə yerləşmir. Növbəti sətirdə xətlərin təsviri verilir: u_j v_j w_j (1 \leq u_j, v_j \leq n, u_j \neq v_j, 1 \leq w_j \leq 10^6), burada u_j və v_j arasında tutumu w_j olan drenaj xətti mövcuddur. Drenaj xətlərinin daxili nöqtələrdə kəsişmədiyi, həmçinin və qovşaqlarının Vasya'nın yerləşdiyi drenaj sahəsindən normal axın rejimində əlçatan olduğu təmin edilir. İki qovşaq arasında ən çox bir drenaj xətti var.
Vasya'nın vahid zamanda axıda biləcəyi maksimum kərə yağı miqdarını çap edin.
Nümunə 1