Lūcija un Džims ir nokļuvuši kosmiskajā kuģī. Kosmosa kuģis sastāv no istabām un gaiteņiem, kas tās savieno. Katram gaitenim ir zināms laiks sekundēs, kāds nepieciešams lai pa to aizietu no vienas istabas uz otru. Divās istabās atrodas teleporti - ierīces, kas ļauj nokļūt no vienas istabas, kurā atrodas teleports, uz otru istabu, kurā atrodas teleports, momentāni. Lūcija K reizes pārvietojās starp dažādu istabu pāriem, katru reizi pierakstot, cik ilgā laikā no vienas istabas izdevās nokļūt līdz otrai. Noteikti vismaz vienu reizi tika lietoti teleporti. Džimam pēc Lūcijas pierakstiem ir jānosaka, tieši kurās istabās atrodas teleporti. Uzrakstiet programmu, kas atrisina šo uzdevumu!

Ievaddatu pirmajā rindā doti divi naturāli skaitļi N(istabu skaits, 1 ≤N≤200) un M(gaiteņu skaits, 1≤M≤20000), kas atdalīti ar tukšumsimbolu. Istabas ir numurētas ar naturāliem skaitļiem no 1 līdz N pēc kārtas. Faila nākošajās M rindās dots pa trim skaitļiem A,B un T, kas atdalīti ar tukšumsimboliem, katrā. Katra šāda rinda nozīmē, ka istabas A un B ir savienotas ar gaiteni un pa šo gaiteni no vienas istabas līdz otrai var nokļūt T sekundēs. Faila nākošajā rindā dots naturāls skaitlis K (1≤K≤5000) - Lūcijas veikto pārvietošanās reižu skaits. Faila nākošajās K rindās dots pa trim skaitļiem A,B un T, kas atdalīti ar tukšumsimboliem, katrā. Katra šāda rinda nozīmē, ka Lūcija no istabas A līdz istabai B nokļuva T sekundēs.

Piezīme: atrisinājums vienmēr ir iespējams un ir viens vienīgs.

Izvaddatu vienīgajā rindā jāizvada divi skaitļi - to istabu numuri, kurās atrodas teleporti. Pirmajam skaitlim jābūt mazākam par otro un starp skaitļiem jābūt vienam tukšumsimbolam.

Uzdevums izmantots Horvātijas informātikas olimpiādē 2003.gadā