P2934 [USACO09JAN] Safe Travel G

小妖精侵占了农场。这些讨厌的类精灵生物会阻挠每头牛从谷仓（位于 $\mathrm{pasture}_1$（牧场 $1$））前往其他牧场的行程，其中第 $i$ 头牛要从 $\mathrm{pasture}_1$ 前往 $\mathrm{pasture}_i$。每个小妖精都经过个性化训练，知道第 $i$ 头牛前往 $\mathrm{pasture}_i$ 的最短路径。第 $i$ 个小妖精会埋伏在第 $i$ 头牛最短路径的最后一条道路上，企图骚扰这头牛。 每头牛当然都不希望被骚扰，因此会选择一条与原始最短路径至少存在细微差别的从 $\mathrm{pasture}_1$ 到 $\mathrm{pasture}_i$ 的新路径。 请计算每头牛避开位于其原始最短路径最后一条道路上的小妖精后，新路线的最短通行时间。 给定 $M (2 \leq M \leq 200\,000)$ 条双向道路（编号 $1\dots M$）连接 $N (3 \leq N \leq 100\,000)$ 个牧场（编号 $1\dots N$）。第 $i$ 条道路连接牧场 $a_i (1 \leq a_i \leq N)$ 和 $b_i (1 \leq b_i \leq N)$，通行时间为 $t_i (1 \leq t_i \leq 1\,000)$。保证没有两条道路连接同一对牧场，且所有测试数据中从 $\mathrm{pasture}_1$ 到任意 $\mathrm{pasture}_i$ 的最短路径唯一。 例如以下牧场、道路和通行时间： ``` 1--[2]--2-------+ | | | [2] [1] [3] | | | +-------3--[4]--4 ``` ``` TRAVEL 最佳路线 最短时间 最后一条道路 p_1 到 p_2 1->2 2 1->2 p_1 到 p_3 1->3 2 1->3 p_1 到 p_4 1->2->4 5 2->4 ``` 当存在小妖精时： ``` TRAVEL 最佳路线 最短时间 规避道路 p_1 到 p_2 1->3->2 3 1->2 p_1 到 p_3 1->2->3 3 1->3 p_1 到 p_4 1->3->4 6 2->4 ``` - 对于 $20\%$ 的测试数据，$N\leq 200$。 - 对于 $50\%$ 的测试数据，$N\leq 3000$。

无

无