Problem C: Seishun 18 Kippu

R大学のとある学生sirokurostoneはA津大学で行われる合宿に参加しようとしていた。 他のメンバーは新幹線を使用する予定なのだが、sirokurostoneは青春18切符を使って向かおうとしていた。 同じく青春18切符使いのとある2D好きな人物も合宿に参加しようとしていた。

どうせならと一緒に行こうと考えたsirokurostoneは途中の駅で2D好きな彼を拾って向かおうと考えた。 sirokurostoneはR大学を出る前に遅延状況を確認してすこしでも時間のかからないルートを通ってA津大学のある駅に着きたいと考えている。 sirokurostoneはルートが確定した後に2D好きな彼にもその情報を伝えるつもりである。 しかし、sirokurostoneは遅延状況を見てもどのルートを通れば早くA津大学のある駅に到着できるか分からず困っている。

そこで、あなたの仕事はsirokurostoneに代わって遅延状況からどれくらいでA津大学のある駅に着くのかを求めることである。

各駅間には、駅間の距離と遅延予想時間がある。 電車は動き始めてから40km/hを維持するものとする。 地点aと地点bの間の移動時間は、

• 距離/40+遅延予想時間

で求めることができる。 各駅での停車時間は無視してよいものとする。

Input

複数のデータセットの並びが入力として与えられる。 データセット数は50以下であることが保障されている。 各データセットは、次の形式をしている。

n m
s p g
a1 b1 d1 t1
...
ai bi di ti
...
am bm dm tm

整数n(3 ≤ n ≤ 500)とm(2 ≤ m ≤ 5000)は、それぞれ駅の数、各駅間の線路の数の合計を表す。 s、p、gは、それぞれsirokurostoneが乗る駅、2D好きな人物が乗る駅、A津大学がある駅の場所を示す文字列である。 s、p、gはそれぞれ違う文字列である。

続くm行は、駅間情報を表す。 a_i、b_iは、線路がつなぐ駅を示す文字列である。 a_iとb_iは、双方向に行き来することができる。 a_iとb_iが一致することはない。 整数d_i(40 ≤ d_i ≤ 10000)は、a_iとb_iの距離を表す。 d_iは40の倍数であることが保証されている。 整数t_i(0 ≤ t_i ≤ 20)は、a_iとb_iの間の遅延予想時間を示す。

駅名を表す文字列は、全てアルファベットの小文字および大文字からなる20文字以下の文字列であらわされる。 駅と駅の間の線路は高々1本である。

入力の終わりは2つのゼロを含む行で表される。

Output

入力データセットごとに、A津大学がある駅への到達時間(単位:時間)を出力せよ。 sirokurostoneが乗る駅から2D好きな人が乗る駅までの経路と、2D好きな人物が乗る駅からA津大学がある駅の場所までの経路があることが保証されている。

Sample Input

4 4
A B G
A B 40 3
B C 80 0
A G 40 0
B G 80 0
5 6
Kusatsu Tokyo Aizu
Tokyo Nagoya 120 3
Kusatsu Nagoya 40 0
Kusatsu Kanazawa 40 0
Kanazawa Aizu 40 0
Tokyo Kanazawa 40 0
Tokyo Aizu 80 4 
0 0

Output for Sample Input

5
4

Note

Commentary

 

---