Like no Tomorrow

夏

老师好，我是爱莉。我们放学后甜点部刚刚结束了在学校的最后一次乐队练习，正准备前往演出场地。不过，去那里的路变得有点复杂了……

从学校去演出场地需要坐公交车，公交车分为普通公交和循环公交，收费方式各不相同。当然，我们可是放学后甜点部，演出前去甜品咖啡馆吃点甜点是必不可少的，对吧？ 但是我们带的钱不多，所以得找到尽量省钱到达演出场地的方法。

夏酱最擅长说明情况了，所以接下来就请夏酱来解释。

在一个有$N$个顶点、$M$条带权边的有向图$G$中，放学后甜点部必须从顶点$1$的学校出发，前往顶点$N$的演出场地。到达演出场地前，必须至少访问一家甜品咖啡馆，并使整个行程的总费用最小。从学校到演出场地的路线一定存在。

除顶点$1$的学校和顶点$N$的演出场地外，其余顶点中有$K$个是甜品咖啡馆。可以任意多次乘坐普通公交或循环公交来移动。但是，一旦乘公交访问了演出场地，就不再前往任何其他地点。 两种公交的规则如下。

• 普通公交

  • 在两个不同地点之间移动时，需要支付与行驶距离相等的费用。
  • 行驶距离为经过的所有边的权值之和。

• 循环公交

  • 仅在彼此可达的顶点之间运行。两个顶点$u, v$彼此可达，是指既存在从$u$到$v$的有向路径，也存在从$v$到$u$的有向路径。
  • 循环公交的费用，为从上车顶点出发后经过的第一条边的权值。
  • 从一个顶点乘循环公交到另一个顶点时，仅将这两个顶点视为已访问，途中经过的其他顶点不视为已访问。

……夏酱让我这样写。

老师，请帮我们求出前往演出场地的最小费用吧。

第二行给出甜品咖啡馆所在顶点的编号，以空格分隔。这些顶点编号均不小于$2$且不大于$N - 1$。

从第三行开始，接下来的$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)$ 对于任意两条不同的边$i, j$，均有$(u_i, v_i) \neq (u_j, v_j)$。

时间限制

2000 ms

内存限制

1024 MB

检查器

CUSTOM