Daxil ol və çıx
Gənc pirat Vil Tvister atasından ona miras qalan qiymətli medalonu itirib. İndi bu medalyon qubernator Guzun əlindədir. Medalyon Vila çox əziz olduğundan, onu geri almağa qərar verir. Onun varlığı asanlıqla fərq edilə bilər (axı o, ninja deyil), buna görə də uğur şansını artırmaq üçün gecənin örtüyündən istifadə edəcək. Bu isə o deməkdir ki, qubernatorun evinə səyahət də təhlükəli olacaq, çünki gecə şəhərdən keçən hər kəs şübhəli sayılır.
Şəhərdə strateji əhəmiyyətli kəsişmələrdə yerləşən çoxlu keşikçilər^1 var. Vil yaxşı döyüşçü deyil, buna görə də onların yanından keçmək üçün qəfil və sürətli hərəkət etməyə güvənəcək. Əgər Vil qubernatorun evinə gedərkən və qayıdarkən eyni keşikçinin yanından iki dəfə keçərsə, qəfil hərəkət faktoru yox olacaq və ikinci keçiddə tutulma riski çox yüksəkdir. Buna görə də o, eyni keşikçinin yanından iki dəfə keçmək istəmir.
Səyahət gəmi ilə gələcəyi və gedəcəyi limandan başlayır. Onun şəhərin bütün keşikçi yerlərinin göstərildiyi xəritəsi var. Çox qaçmalı olacağını nəzərə alaraq, o, qubernatorun evinə gedən və qayıdan ən qısa marşrutu tapmaq istəyir ki, bu marşrut heç bir keşikçinin yanından iki dəfə keçməsin. Ona belə bir yolu tapmağa kömək edə bilərsinizmi?
_______
^1 - keşikçi - bu, stasionar mühafizəçidir.
Giriş verilənləri
Birinci sətir testlərin sayını ehtiva edir. Hər bir test aşağıdakı formatda olur:
Birinci sətir kəsişmələrin sayı n və yolların sayı r (2 ≤ n ≤ 1000, 1 ≤ r ≤ 10000).
r sətir üç ədəd a, b və l (1 ≤ a, b ≤ n, 1 ≤ l ≤ 1000) verən, kəsişmələr a və b arasında uzunluğu l olan iki istiqamətli yolu təyin edir.
Kəsişmələrin sayını göstərən sətir S (0 ≤ S ≤ min(N-2, 100)).
S müxtəlif tam ədədlər s_i (2 ≤ s_i < n) olan sətir, s_i kəsişməsində keşikçinin olduğunu göstərir.
Kəsişmələr 1 -dən n -ə qədər nömrələnib. Vilin gəmisi 1 kəsişməsində, qubernatorun evi isə n kəsişməsindədir. Gəmidən qubernatorun evinə yolun mövcud olduğu təmin edilir.
Çıxış verilənləri
Hər bir test üçün Vilin qət etməli olduğu ən kiçik cəmi məsafəni ayrıca sətirdə çıxarın. Əgər hər bir keşikçinin yanından bir dəfədən çox keçməyən marşrut mövcud deyilsə, "No safe route" (tırnaq işarələri olmadan) çıxarın.