Cerința

Suntem în anul 2050. Compania U.S. Robotics and Mechanical Men a finalizat proiectul de creare a primului motor superluminic, care acum se află în pragul de testare. Pentru această sarcină a fost ales un model QT-1 de robot pozitronic care urmează să piloteze nava cu motorul superluminic încorporat și să raporteze randamentul de funcționare al acestuia.

Sectorul ales pentru testarea zborului interstelar constă într-o secțiune din galaxie alcătuită din n sisteme solare, conectate între ele prin rute hiperspațiale unidirecționale de un anumit cost energetic (care poate fi și negativ). La rândul lui, fiecare sistem solar este dispus sub forma unei configurații de s-1 rute interplanetare ce unesc toate planetele din acesta astfel încât să se evite formarea de cicluri în continuumul spațiu-timp. Ciclurile în continuumul spațiu-timp nu se pot forma atâta timp cât drumul de lungime minimă dintre oricare două planete din același sistem solar este unic.

Randamentul pe care trebuie să-l monitorizeze QT-1 se definește ca valoarea minimă a costului energetic suportat de motor ce se poate obține în urma salturilor prin hiperspațiu pornind de la sistemul solar al Pământului, x, și ajungând la cel ales drept destinație, y. Însă, cum circuitele pozitronice ale robotului sunt extrem de sensibile în raport cu configurația rutelor interplanetare ale unui sistem solar, QT-1 urmează să traverseze exclusiv sisteme solare echivalente structural cu cel de origine.

Ajutați-l pe QT-1 să afle randamentul motorului obținut pe traseul optim de traversare a galaxiei, iar, dacă nu există un astfel de randament, atunci ajutați-l să concluzioneze că succesiunea de salturi hiperspațiale a fost întreruptă de o gaură neagră. Definim o gaură neagră drept o succesiune de salturi prin hiperspațiu între sisteme solare echivalente structural cu cel de origine, care începe și se termină în același sistem solar și in urma căreia randamentul motorului scade, provocând colapsul lui QT-1 in eter. Însă, dacă QT-1 nu poate ajunge la o gaură neagră detectată aceasta nu va fi raportată, deoarece nu va influența traseul robotului.

De voi depinde viitorul omenirii!

Date de intrare

Pe prima linie a fișierului stardust.in se află n – numărul de sisteme solare, m – numărul de rute interstelare, x și y – sistemul origine, respectiv destinație și s – numărul de planete din fiecare sistem solar.

Pe următoarele m linii se află triplete de forma u, v, w, cu proprietatea că există rută unidirecțională prin hiperspațiu, de cost w, de la sistemul solar u la sistemul solar v.

În continuare se vor citi, în ordine de la 1 la n, configurațiile de rute interplanetare corespunzătoare fiecărui sistem solar: câte s-1 linii pe care se găsesc perechi de forma p, q, cu proprietatea că există rută interplanetară bidirecțională de la planeta p la planeta q a respectivului sistem solar.

Date de ieșire

Pe prima linie a fișierului stardust.out se va afișa W – randamentul înregistrat pe drumul optim dintre sistemele x și y.

Dacă nu există un astfel de randament, se va afișa mesajul Black hole detected! .

Restricții și precizări

• 1 ≤ n ≤ 1.000
• 2 ≤ s ≤ 100
• 1 ≤ n ≤ m ≤ 28.000
• |w| ≤ 10.000
• 1 ≤ u, v ≤ n
• 1 ≤ p, q ≤ s
• Sistemele solare sunt indexate de la 1 la n.
• Planetele din fiecare sistem solar sunt indexate de la 1 la s.
• Două sisteme solare A = (V1, E1) și B = (V2, E2) sunt echivalente structural dacă și numai dacă există o bijecție f : V1 -> V2 asftel încât: \( (u,v \in V1, [u,v] \in E1) <=> (f(u),f(v) \in V2, [f(u),f(v)] \in E2) \).
• Se garantează că există în cadrul fiecărui test cel puțin un lanț elementar format din sisteme solare echivalente structural ce unește sistemele x și y.
• Se recomandă parsarea fișierului de intrare

Exemplu:

stardust.in

5 6 3 5 4
2 5 7
1 4 -4
4 5 4
3 2 3
3 1 -2
2 4 2
1 2
2 3
4 3
1 2
2 3
2 4
1 2
1 3
1 4
1 3
2 3
4 3
4 1
2 4
4 3

stardust.out

9  

stardust.in

5 5 1 5 2
1 2 99
2 3 10
3 4 20 
4 2 -31
1 5 0
1 2
1 2
2 1
2 1
1 2

stardust.out

Black hole detected!

Explicație

În primul exemplu toate sistemele solare sunt echivalente structural între ele mai puțin primul, astfel traseul valid de cost minim fiind 3 -> 2 -> 4 -> 5.

În al doilea exemplu toate sistemele solare sunt sunt echivalente între ele, însă se formeaza o gaură neagră între sistemele solare 2, 3 și 4.