rt，如果把这道题边权改为 $a\times 2^b$，其中 $a$ 是1e9 $b$ 是1e5 答案对质数取模怎么做

可以认为1s可以2e9~5e9

注意是输出最短路对质数取模的值而不是取模意义下最短路的值