Robotlar və neft kəmərləri

Bəzi ölkələrdə neftin nəql edilməsinin nəhəng sistemi var. Bu sistem bəzi cütləri borularla birləşdirilmiş çoxlu sayda nəzarət stansiyaları kimi təsvir olunur.

Sistem əvvəldən əlaqəlidir, başqa sözlə, istənilən stansiyadan ixtiyari digərinə boru vasitəsilə yol var. Lakin sistemdə elə borular var ki, onlardan ixtiyari birinin üstünün ötürülməsi sistemin əlaqəliliyinin pozulmasını göstərir. Belə borular magistral borular adlanır. Heç olmasa bir magistral borunun olmasına təminat verilir.

Magistral borulara xidmət üçün kompaniya iki robot aldı. Komanda alınan kimi hər hansı magistral boru seçilir və hər iki robot onun müxtəlif uclarına tərəf hərəkətə başlayırlar. Hər robot üçün həmin robotun öz təyin olunduğu nöqtəyə digərindən mümkün gec çatdığı vaxta gəlib çatma vaxtı sayılır.

Robotlar boruların yanı ilə hərəkət edirlər və vahid zamanda vahid məsafə qət edirlər. Komanda alınan anda robotlar verilmiş nəzarət stansiyalarında(mümkündür ki, müxtəlif stansiyalarda) yerləşirlər.

Robotların gəlib çatma vaxtı minimum olan magistral borunu müəyyənləşdirən proqramı yazın.

Giriş verilənləri

Giriş faylının birinci sətrində uyğun olaraq nəzarət stansiyalarının və boruların sayı olan iki tam N (2 <= N <= 100000) və M (2 <= M <=100000) ədədləri verilir. Sonrakı M sayda sətrin hər birində üç tam ədəd - iki nəzarət stansiyasının nömrələri və onları birləşdirən boruların uzunluğu verilir. Boruların uzunluğu 1000-i aşmır.

(M+2)-ci sətirdə iki tam ədəd komanda alındığı vaxt robotların olduğu nəzarət stansiyalarının nömrələri verilir.

Çıxış verilənləri

Robotların magistral borulara gəlib çatmasının minimum vaxtı olan bir tam ədəd çıxışa verilir.