もんだい！
πくんは友達がいっぱいいる 幸せなことだ。
πくんは、よく友達の家に遊びにいく。
でも、πくんは友達の家に向かう途中、疲れることや、時間がかかってしまうことに対して、ストレスを感じるらしい。
ストレスがたまると良くないので、できるだけストレスが少ない道を行きたいと考えた。
πくんが、ある友達の家に行くまでの間に感じるストレスは、疲れること、または時間がかかってしまうことのどちらか一方の、値の小さい方のみになる。両方のストレスを同時に感じることはない。
また、道の方向は決められていない。
感じるストレスの最小をπくんに教えてあげてほしい。
入力
n m a0 b0 c0 t0 a1 b1 c1 t1 . . am-1 bm-1 cm-1 tm-1 d x0 y0 e0 p0 x1 y1 e1 p1 . . xd-1 yd-1 ed-1 pd-1
1 行目には、友達の数 n と、道のデータの数 m が与えられる。
2 行目から m+1 行目には、友達の家 a から 友達の家 b まで、疲れが c 、時間が t かかることを表すデータが入力される。
m+2 行目には、友達の家に遊びに行く日数が与えられる。
続く m+3 行目からは、πくんがいる場所 x と、そこから行きたい友達の家 y と、疲れが 1 かかる時のストレス e と、時間が 1 かかる時のストレス p があたえられる。
テストケースにおいて、道が繋がっていない友達の家はないものとする。
出力
それぞれの日に、πくんが感じるストレスの最小値を出力してね。
制約
3 ≦ n ≦ 500
n - 1 ≦ m ≦ min((n*n-n)/2, 50000)
1 ≦ a,b ≦ n
1 ≦ c,t ≦ 1000
1 ≦ d ≦ 1000
1 ≦ e,p ≦ 100
入出力例
入力例
4 5 1 3 3 10 3 4 10 2 4 2 8 1 2 1 2 5 1 4 5 8 3 1 4 3 2 2 4 1 1 3 2 3 9
出力例
12 1 15
解説
下の図のような形のデータである。
1 から 4 までの最小の疲れは 5 、時間は 6 になる。
そこに、ストレスをかけてあげると、それぞれ 15 と 12 になるので、小さい方を出力する。
