005 - πくんのもんだい

もんだい！

πくんは友達がいっぱいいる 幸せなことだ。

πくんは、よく友達の家に遊びにいく。

でも、πくんは友達の家に向かう途中、疲れることや、時間がかかってしまうことに対して、ストレスを感じるらしい。

ストレスがたまると良くないので、できるだけストレスが少ない道を行きたいと考えた。

πくんが、ある友達の家に行くまでの間に感じるストレスは、疲れること、または時間がかかってしまうことのどちらか一方の、値の小さい方のみになる。両方のストレスを同時に感じることはない。

また、道の方向は決められていない。

感じるストレスの最小をπくんに教えてあげてほしい。

入力

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 になるので、小さい方を出力する。