問題文

kazuppa町には $N$ 個の地点と $R$ 個の道があります。道 $i$ では地点 $U_i$ と地点 $V_i$ を双方向に移動することができ、徒歩で移動するには $W_i$ 分、オートマ車で移動するには $A_i$ 分、マニュアル車で移動するには $M_i$ 分かかります。道の移動にはそれ以外の交通手段はありません。

また、kazuppa町は海に面しているため、各地点を船で移動することができます。地点 $i$ から地点 $j$ に船を使って移動するのには $S_i+S_j+C$ 分が必要です。

また、各地点では免許を取ることができます。地点 $i$ でオートマ限定免許を取るには $X_i$ 分、マニュアル免許を取るには $Y_i$ 分、船舶免許を取るには $Z_i$ 分必要です。

kazuppa町では所持している免許に応じて以下のように交通手段を使うことができます。

• 車の免許をどちらも持っていない場合、道の移動は徒歩のみ使用可能。
• オートマ限定免許を持っているがマニュアル免許を持っていない場合、道の移動は徒歩またはオートマ車のみ使用可能。
• マニュアル免許を持っている場合、道の移動は徒歩またはオートマ車またはマニュアル車が使用可能。
• 船舶免許を持っている場合のみ、船が使用可能。

Bread君は始め地点 $1$ にいて、免許をどれも持っていません。適切な行動を取った時、最小何分で地点 $N$ に到着できるかを求めてください。

制約

• $1\leq N\leq 30000$
• $1\leq R\leq 60000$
• $1\leq C\leq 10^{14}$
• $1\leq X_i,Y_i,Z_i\leq 10^9$
• $1\leq S_i\leq 10^{14}$
• $1\leq U_i< V_i\leq N$
• $1\leq W_i,A_i,M_i\leq 10^9$
• 入力はすべて整数

小課題

この問題にはサブタスクによる部分点が設定されています。

入力

$N\ R\ C$
$X_1\ X_2\ \dotsc\ X_N$
$Y_1\ Y_2\ \dotsc\ Y_N$
$Z_1\ Z_2\ \dotsc\ Z_N$
$S_1\ S_2\ \dotsc\ S_N$
$U_1\ V_1\ W_1\ A_1\ M_1$
$U_2\ V_2\ W_2\ A_2\ M_2$
$\vdots$
$U_R\ V_R\ W_R\ A_R\ M_R$

出力

答えを一行に出力してください。

サンプル

5 6 2
10 100 1 1000 10000
10 1 100 1000 10000
1 1 1 1 1
10000 1000 100 10 1
1 2 10 10 10
1 3 1 1 1
1 4 10 10 10
2 3 10 1 1
2 4 10 10 1
3 4 10 10 10

19