006 - 大ドイツ主義

入出力例1に誤りがありましたので、修正とリジャッジをしました。
これによるAC者の変動はありません。

問題

ここはドイツだ。
ドイツにはアウトバーンと呼ばれる速度無制限の高速道路がある。
ドイツには0〜Vと番号づけられたの都市があり、2つの都市を双方向にむすぶ道路がE本ある(ある都市a, bを結ぶ道路は重複しない)。また道路E_iを通るためには通行料としてc_iレンテンマルクがかかる。
さて、ドイツにはヒットレルという首相兼大統領がいる。
彼は国内の産業を活発にしたいので通行料を半分(小数点以下切り捨て)にしようと考えた。
早速彼はN人いる道路の管理者にその旨を通知した。
しかし、管理人たちは利益が減ってしまうこの政策には困ってしまった。
かといって実施しないと強制収容所に収容されてしまう。
そこで、通行した人の知り合いの知り合いの……知り合いが通行する道路の管理者ならば半額にするという協定を結んだ。
あなたはダンツィヒにおり、エルザス＝ロートリンゲンに行きたい。
この時払わなければいけない最小の金額を求めよ。
ただしどうやっても辿り着けないなら NA を出力せよ。

入力

V E N
a1 b1 c1 d1
……………
aE bE cE dE
Q
Ai Bi
AQ BQ
S G

まず、都市の数V, 道路の数E, 管理者の数Nが入力される。
その後、E行にわたって道路E_iが結ぶ2都市a, b、通行料c, 管理者の番号dが入力される。
Q行にわたって知り合い関係が入力される。
ここでのa, bは番号A, 番号Bが知り合いであることを示す。なお0番目はあなたを意味する。
最後にダンツィヒとエルザス＝ロートリンゲンがそれぞれ何番の都市であるかを示すS, Gが入力される。

出力

ans

NAまたは最小の金額を出力する。
最後の改行を忘れずに。

制約

$1 \leq V \leq 10^3$
$1 \leq N \leq 10^3$
$1 \leq E \leq 5 \times 10^5$
$1 \leq Q \leq 10^3$
$0 \leq a_i \leq V$
$0 \leq b_i \leq V$
$a_i \neq b_i$
$0 \leq G \leq V$
$0 \leq S \leq V$
$S \neq G$
$2 \leq c_i \leq 10^3$
$1 \leq d_i \leq N$
$0 \leq A_j \leq N$
$0 \leq B_j \leq N$
$A_j \neq B_j$
$1 \leq i \leq E$
$1 \leq j \leq N$
1人の管理人が管理する道路の個数は0以上M以下。 入力はすべて整数。

テストケース

例1

入力

9 14 10
1 2 2 1
2 3 5 1
2 3 6 2
1 4 1 3
2 4 1 1
2 5 2 1
3 5 4 3
3 8 3 2
5 8 4 3
5 8 3 2
4 5 6 3
4 7 3 1
4 6 2 2
7 8 2 1
3
4 1
4 9
0 9
1 8

出力

3

例2

入力

7 7 8
1 2 2 1
1 3 5 2
1 4 4 3
2 4 3 4
3 4 2 5
2 5 6 6
4 5 2 7
1
1 2
1 6

出力

NA