Like no Tomorrow

ナツ

こんにちは、先生。アイリです。私たち放課後スイーツ部は、学校で最後のバンド練習を終えて、これからライブ会場へ向かうところです。でも、会場までの道のりが少し複雑になってしまって……。

学校から会場まではバスに乗る必要があるんですが、普通のバスと循環バスがあって、それぞれ料金が違うんです。もちろん、私たちは放課後スイーツ部ですから、本番前に甘いスイーツのカフェに寄るのは欠かせませんよね？ でも、あまりお金がないので、できるだけ節約して会場へ行く方法を探さないといけないんです。

状況を説明するのはナツちゃんが一番上手なので、ここからはナツちゃんにお願いしました。

頂点が$N$個、重み付き辺が$M$本ある有向グラフ$G$において、放課後スイーツ部は頂点$1$の学校を出発し、頂点$N$のライブ会場へ向かわなければならない。会場に到着する前に必ず1つ以上のスイーツカフェを訪れ、その道中の総費用を最小にする必要がある。学校から会場へ行く方法は必ず存在する。

頂点$1$の学校と頂点$N$の会場を除いた頂点のうち、$K$個がスイーツカフェの頂点である。普通のバスと循環バスを、好きな回数乗り継いで移動できる。ただし、バスで会場を訪れたら、それ以降は他の場所へ移動しない。 バスには次の2種類がある。

• 普通のバス

  • 異なる2つの場所の間を移動する際、移動距離と同じ額の運賃を支払う。
  • 移動距離は、通った辺の重みの総和である。

• 循環バス

  • 互いに行き来できる頂点の間だけを運行する。2つの頂点$u, v$が互いに行き来できるとは、$u$から$v$への有向パスと、$v$から$u$への有向パスの両方が存在することをいう。
  • 循環バスの運賃は、乗車した頂点から最初に通る辺の重みとなる。
  • ある頂点から循環バスで別の頂点へ移動するとき、その2頂点だけを訪れたものとし、途中の頂点は訪れたものとしない。

……と、ナツちゃんが書くように言っていました。

先生。私たちのために、会場へ行くのにかかる最小費用を求めてください。

2行目に、スイーツカフェがある頂点の番号が空白区切りで与えられる。これらの頂点番号は$2$以上$N - 1$以下である。

3行目から$M$行にわたって辺の情報が与えられる。そのうち$i$行目には$u_i$、$v_i$、$c_i$が空白区切りで与えられ、頂点$u_i$から頂点$v_i$へ、重み$c_i$の有向辺があることを表す。$(1 \le u, v \le N$; $u \neq v$; $1 \le c_i \le 1\,000)$ 異なる2本の辺$i, j$について、$(u_i, v_i) \neq (u_j, v_j)$である。

実行時間制限

2000 ms

メモリ制限

1024 MB

チェッカー

CUSTOM