考虑最终可能的答案，有以下几种形式：$xa$，$ya + zb$（$y \in \{0, 1\}$），$wb$。

前两种可以使用一遍 BFS 计算，关键在于第三种，不惜多用几个 $b$ 的代价来换取 $a$ 的减少。考虑接着用 BFS 计算，因为边权还是相等的。过程形如：

• $u$，出队
  • 枚举 $u \to v$（$\mathcal O(m)$）
    • 枚举 $v \to w$（$\mathcal O(m)$）
      • 如果 $w \not\in \{v\}$：更新 $w$，入队

这会在菊花上被卡满，$\mathcal O(m^2)$。因此考虑优化。

事实上一个 $w$ 只可能被更新一次，因此我们枚举 $v \to w$ 时一旦成功松弛则可以删去 $v \to w$ 的边（但是 $u \to v$ 不能删去，因此我们 只在第二层 遍历一个可删的边表。链式前向星不难实现）。

时间复杂度：考虑如果 $w \in \{v\}$ 会发生什么：$u, v, w$ 构成了三元环。否则就是均摊 $\mathcal O(1)$ 的（神奇吗？）。因为三元环的个数为 $\mathcal O(m^{1.5})$ 个，因此总时间复杂度为 $\mathcal O(n + m^{1.5})$。

常数被 xhz 卡爆了。