Tək istiqamətli küçə

Einbahnstraße (Almancada bir istiqamətli küçə deməkdir) — avtomobillərin yalnız bir istiqamətdə hərəkət edə bildiyi küçədir. Bir istiqamətli küçələrin əsas səbəblərindən biri sıx ərazilərdə nəqliyyat axınının daha rahat olmasını təmin etməkdir. Bu, xüsusilə şəhər mərkəzlərində, xüsusilə də Qahirə və Dəməşq kimi qədim şəhərlərdə faydalıdır. Diqqətlə planlaşdırılan belə küçələr istənilən məntəqədən hər hansı digər məntəqəyə çatmağı təmin edir. Bununla belə, sürücülər marşrutlarını diqqətlə planlaşdırmalıdırlar, yoxsa bir istiqamətli küçələr üzündən yollarını uzada bilərlər. Təcrübəli sürücülər bilirlər ki, istənilən iki məntəqə arasında bir neçə yol mövcuddur. Bundan başqa, eyni iki məntəqə arasında bir neçə yol ola bilər. İki məntəqə arasında ən qısa yolu bilmək vacibdir! Bu, xüsusilə idarə olunması çətin olan nəqliyyat vasitələri (zibil maşınları, evakuatorlar və s.) üçün daha da vacibdir.

Sən bir avtomobil evakuasiyası şirkətində yeni işə başlamısan. Şirkətə məxsus bir neçə evakuator şirkətin qarajında dayanır. Evakuator nasaz avtomobilin ön və ya arxa təkərlərini qaldırır və onu düz şirkətin qarajına aparır. Sən şəhərin müxtəlif yerlərindən nasaz avtomobillərin daşınması üçün zənglər qəbul edirsən. Avtomobillər zənglərin ardıcıllığına görə aparılmalıdır. Sənin vəzifən evakuator sürücülərinə bütün nasaz avtomobilləri toplamaq və onları şirkət qarajına gətirmək üçün ən qısa marşrutu məsləhət verməkdir. Günün sonunda isə sürücülərin ümumilikdə nə qədər yol getdiyini rəhbərliyə bildirməlisən.

Giriş

Proqramın bir və ya bir neçə test nümunəsi üzərində yoxlanılacaq. Hər test nümunəsinin birinci sətrində ardıcıl olaraq $N$, $C$ və $R$ ədədləri verilir. Şəhərdə şirkət qarajı da daxil olmaqla $N$ unikal məntəqə var. $C$ - nasaz avtomobillərin sayı, $R$ isə şəhərdəki yolların sayıdır. Qeyd: 0 < N < 100, 0 \leq C < 1000, və R < 10000. İkinci sətrdə C + 1 söz var: birincisi şirkətin qarajının adıdır, qalanlar isə nasaz avtomobillərin yerləşdiyi məntəqələrdir. Məntəqənin adı ən çox $10$ hərfdən ibarət olan sözdür. Böyük və kiçik hərf fərqləndirilir.

İkinci sətrdən sonra $R$ sətrdən ibarət yol təsviri veriləcək. Hər yol aşağıdakı üç formatdan biri ilə təsvir olunur:

A -v -> B

A <-v - B

A <-v -> B

$A$ və $B$ fərqli iki məntəqənin adıdır, $v$ isə yolun uzunluğunu göstərən $1000$-dən böyük olmayan müsbət tam ədəddir. Birinci format $A$-dan $B$-yə bir istiqamətli küçəni göstərir, ikinci format $B$-dən $A$-ya bir istiqamətli küçəni, üçüncü format isə onların arasında iki istiqamətli küçəni göstərir. $A$, ox və $B$ arasında bir və ya bir neçə boşluq ola bilər.

Test nümunələrinin sonu ($N$, $C$, $R$ üçün) üç sıfırdan ibarət sətrlə göstərilir.

Aşağıdakı nümunədəki test eyni zamanda şəkildəki vəziyyətə uyğundur.