Niedawno, niedawno temu na pewnej uczelni, pewnym wydziale uczył pewien doktor Smokiem przez wtajemniczonych zwany.
Dnia pewnego rzekł ów doktor do studentów swoich: „ponieważ uczyłem was cały rok a postępów nijakich nie widzę przeto w wolny czas wakacyjny uczyć się będziecie a zadania rozwiązywać będzie wam dane, które sam osobiście wam ułożę.” Strach blady padł na studentów lecz nic począć nie mogli, gdyż przez egzaminacyjne sito kilku jeno przedrzeć się było dane.
Rozjechali się zatem studenci do domów swoich z sercami ciężkimi i cięższymi jeszcze zestawami zadań. Lecz ponieważ duch w nich żył studencki szybko przez sieć Internetem zwaną poczęli szukać zbawcy mąk swoich. Dane im było zbawcę tego odnaleźć a choć usługi jego drogie bardzo były pragnienie ukończenia studiów wielkie mieli i gotów byli z uciech nawet zrezygnować aby jeno zadania mieć rozwiązane.
Lecz problem wynikł dla studentów, który bardzo ich trapił – jakże dotrzeć do wybawiciela. Zwracają się do was przeto, braci studencka o pomoc abyście im w tym zadaniu pomogli. Studenci mapę kraju swego mają w elektronicznej postaci na której miast jest M a dróg między nimi D. Drogi wszelkie dwukierunkowe są coby się wszędzie prędko dotrzeć dało a każda z nich długość Wi posiada i dwa miasta łączy Dmi1 i Dmi2. Zbawca ich mieszka w mieście K a oni sami w miastach T1-Ts (studentów zatem S jest). Wszelkie dane zaszyfrowane zostały w numery coby w ręce Smoka straszliwego nie wpadły. Zadaniem twym jest dla każdego studenta długość Li drogi jego do zbawcy wyznaczyć lub ogłosić światu, że student ten zdać nie ma szansy...
Pierwsza linia zawiera liczbę zestawów danych do rozwiązania:
Każdy zestaw składa się z następujących danych:
Zakresy danych:
Dla każdego zestawu danych program powinien na standardowe wyjście wypisywać następujące dane:
2 4 4 1 2 1 2 3 2 2 4 3 3 4 6 4 3 1 2 3 3 1 2 3 2 3 2 1 2
4 3 5 -1 2