非常抱歉这题原数据过弱导致很多人认为 SPFA 做同余类最短路是对的，否则我都不想管这破题了

3 2
100000 100001
2 2
5 4
100000000000
100000000001

100001000000
100000999999

原理和网格图卡 SPFA 类似。

SPFA 的各种玄学优化需要具体情况具体分析。