#215880. [JOI 2015 Final] 鉄道旅行

JOI 国には 個の都市があり，それぞれ の番号が付けられている．また，鉄道が 本あり，それぞれ の番号が付けられている．鉄道 () は，都市 と都市 を双方向に結んでいる．

JOI 国の鉄道に乗車する方法として，紙の切符で乗車する方法と，IC カードで乗車する方法がある．

• 鉄道 に紙の切符で乗車する場合の運賃は 円である．
• 鉄道 に IC カードで乗車する場合の運賃は 円である．ただし，IC カードで鉄道 に乗車するには，鉄道 で使える IC カードを事前に購入しておく必要がある．鉄道 で使える IC カードを購入するには 円かかる．一度購入した IC カードは，何度でも使用することができる．

IC カードの方が金額の処理が簡単になるため，IC カードで乗車する場合の運賃の方が紙の切符で乗車する場合の運賃よりも安い．すなわち， に対して， が成り立つ．IC カードの仕様は鉄道ごとにすべて異なるため，どの に対しても，鉄道 で使える IC カードを他の鉄道で使用することはできない．

あなたは，JOI 国じゅうを旅行することにした．都市 から出発し， の順に都市を訪れる予定である．旅行は 日間の行程からなる． 日目 () に都市 から都市 に鉄道で移動する．この際，いくつかの鉄道を乗り継いで移動することもある．また，同じ都市を二度以上訪れることがあるかもしれない．JOI 国の鉄道は速いので，どの都市からどの都市へも 1 日で移動することができる．

あなたは現在，どの鉄道の IC カードも持っていない．あなたは，あらかじめ，いくつかの鉄道の IC カードを購入し，この旅行にかかる金額，すなわち，IC カード購入費用と乗車した鉄道の運賃の和をできるだけ少なくしたい．

課題

JOI 国の都市の数，旅行の行程，および JOI 国のそれぞれの鉄道の運賃と IC カードの価格が与えられる．このとき，旅行にかかる金額の最小値を求めるプログラムを作成せよ．

標準入力から以下のデータを読み込め．

• 1 行目には，整数 が空白を区切りとして書かれている．これらはそれぞれ，JOI 国に都市が 個あり，旅行が 日間の行程からなることを表す．
• 2 行目には， 個の整数 が空白を区切りとして書かれている．これらは， 日目 () に都市 から都市 に鉄道で移動することを表す．
• 続く 行のうちの 行目 () には，3 つの整数 が空白を区切りとして書かれている．これらはそれぞれ，鉄道 に紙の切符で乗車したときの運賃が 円，IC カードで乗車したときの運賃が 円，鉄道 で使える IC カードの金額が 円であることを表す．

標準出力に，旅行にかかる金額の最小値を円単位で表す整数を 1 行で出力せよ．

样例输入 1

4 4
1 3 2 4
120 90 100
110 50 80
250 70 130

样例输出 1

550

样例输入 2

8 5
7 5 3 5 4
12 5 8
16 2 1
3 1 5
17 12 17
19 7 5
12 2 19
4 1 3

样例输出 2

81

入出力例 1

この場合，旅行にかかる金額を最小にする方法は以下のとおりである．

• 鉄道 2 と鉄道 3 の IC カードを購入する．これには 円かかる．
• 1 日目に，都市 1 から都市 2 まで紙の切符を使って移動し，次に都市 2 から都市 3 まで IC カードを使って移動する．これには 円かかる．
• 2 日目に，都市 3 から都市 2 まで IC カードを使って移動する．これには 円かかる．
• 3 日目に，都市 2 から都市 3 まで IC カードを使って移動し，次に都市 3 から都市 4 まで IC カードを使って移動する．これには 円かかる．

このように移動すると，旅行にかかる金額の合計は 円となる．これが最小であるので， と出力する．

制限

すべての入力データは以下の条件を満たす．

• ．
• ．
• ()．
• ()．
• ()．
• ()．

小課題

小課題 1 [20 点]

以下の条件を満たす．

• ．
• ．
• ()．
• ()．

小課題 2 [30 点]

以下の条件を満たす．

• ．
• ．
• ()．
• ()．

小課題 3 [50 点]

追加の制限はない．