AT_abc232_g [ABC232G] Modulo Shortest Path

[problemUrl]: https://atcoder.jp/contests/abc232/tasks/abc232_g $ N $ 頂点の有向グラフがあります。$ N $ 個の頂点はそれぞれ頂点 $ 1 $、頂点 $ 2 $、$ \ldots $、頂点 $ N $ と呼ばれます。 $ 1\ \leq\ i,\ j\ \leq\ N $ かつ $ i\ \neq\ j $ を満たす整数の組 $ (i,\ j) $ それぞれに対して、 頂点 $ i $ を始点、頂点 $ j $ を終点とする重み $ (A_i\ +\ B_j)\ \bmod\ M $ の有向辺があります。 （ただし、$ x\ \bmod\ y $ は $ x $ を $ y $ で割ったあまりを表します。） 上記のほかに辺はありません。 頂点 $ 1 $ から頂点 $ N $ への最短距離、すなわち、頂点 $ 1 $ から頂点 $ N $ へのパス上の辺の重みの総和として考えられる最小値を出力してください。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 2\ \leq\ M\ \leq\ 10^9 $ - $ 0\ \leq\ A_i,\ B_j\