P8063 [BalkanOI 2012] Shortest paths

Bit 镇的你要去 Hex 镇找你的 npy。

你所在的国家有 $n$ 个镇（镇从 $1$ 到 $n$ 编号），$m$ 条双向道路，Bit 镇在 $a$ 点，Hex 镇在 $b$ 点。每条道路有一个长度。你很了解周围的地图，所以找到了两个镇之间的最短路径，而且，决定将这条路径称为幸运路径。 有一天，政府决定在公路上施工，为了维持交通，决定每次只关闭一条道路（关闭后道路不可通行）。 对于这条幸运路径上的每一条道路，你想知道当这条道路正在关闭时从 Bit 镇到 Hex 镇的最短距离。

无

无

#### 数据范围： Subtask#0 为样例。 $1\le n\le 2000$，$1\le m\le10^5$，$1\le u_i,v_i\le n$，$1\le w_i\le10^5$。 对于 $i\neq j$，满足 $u_i\neq u_j$ 或 $v_i\neq v_j$。 #### 样例解释：  封闭道路 $(1,2)$ 后从点 $1$ 的 Bit 镇无法到达点 $5$ 的 Hex 镇。 封闭道路 $(2,3)$ 后从点 $1$ 的 Bit 镇到点 $5$ 的 Hex 镇的最短路为 $1\rightarrow 2\rightarrow5$，长度 $1+100=101$。 封闭道路 $(3,5)$ 后从点 $1$ 的 Bit 镇到点 $5$ 的 Hex 镇的最短路为 $1\rightarrow 2\rightarrow3\rightarrow4\rightarrow5$，长度 $1+3+3+3=10$。