CF1915G Bicycles

给定 $n$ 个城市和 $m$ 条连接两个城市 $u_i$ 和 $v_i$ 的双向道路，长度为 $w_i$。 现在城市 $n$ 举办了一场派对，住在城市 $1$ 的 Slavic 想要去参加。在城市之间往返需要骑自行车，而 Slavic 没有自行车，所以他需要在这些城市里购买自行车以赶到城市 $n$。 从 $1$ 到 $n$ 的每个城市 $j$ 里都有且仅有一辆自行车可供购买，每辆自行车的速度系数为 $s_j$。 当 Slavic 骑上编号为 $j$ 的自行车后，他可以在任何时刻和任何地点通过一条道路 $i$，花费 $w_i\times s_j$ 的时间。 求 Slavic 骑车从城市 $1$ 赶到城市 $n$ 参加派对所需的最短时间。

无

无

$ 2 \leq n \leq 1000 $，$ n - 1 \leq m \leq 1000$，$ 1 \leq s_i \leq 1000 $； $ 1 \le u_i, v_i \le n $ , $ u_i \neq v_i $，$ 1 \leq w_i \leq 10^5$； 所有测试数据的 $\sum n$、$\sum m$ 不超过 $1000$。 保证存在方案能从城市 $1$ 到达城市 $n$。 By Misaka16172