果冻有一份世界地图，上面标注了各魔法传送点及传送点两两间的传送路线，有一些路线是双向的、另外一些是单向的。如果传送路线是双向的，果冻可以从该路线的两点中任一点传送到另一点；如果传送路线是单向的，果冻只能从起点传送到终点。
由于极其特殊的气候，当前季节很长时间内恒定会出现一天雨天、一天晴天的循环交替。每次传送都需要消耗魔法。晴雨不同会影响魔法流，因此晴雨不同时，传送消耗的魔法也可能不同。
果冻听闻在某个传送点附近居住着名为禾枫的贤者，于是他打算前往拜访贤者。果冻当前在传送点 1 ，当天是晴天。从当天开始(含当天)，果冻每天都可以使用至多一次传送。由于果冻的魔法量很低，他想要在到达目的地时总消耗最小，请算出最小消耗。
例如，假设有传送点间情况如下表，想前往传送点 5 ，最小消耗是 19 。
| 起点 | 终点 | 是否双向 | 晴天消耗 | 雨天消耗 |
|---|---|---|---|---|
| 1 | 3 | Y | 10 | 20 |
| 3 | 5 | Y | 10 | 22 |
| 2 | 1 | N | 1 | 2 |
| 3 | 2 | N | 10 | 2 |
| 2 | 4 | Y | 4 | 8 |
| 3 | 4 | Y | 30 | 32 |
| 1 | 4 | Y | 34 | 30 |
| 4 | 5 | Y | 15 | 3 |
假设有 n=1437 个传送点， m=4096 条传送路线。第 i 条传送路线的起点 u_i 是 ((1399i^2+u_{i-1}^2)\bmod n)+1 ，终点 v_i 是 ((1427i^2+v_{i-1}^2)\bmod n)+1 ，特别地，当计算得 u_i=v_i 时，令 u_i=(u_i\bmod m)+1。若 i 为奇数是双向传送路线；否则是单向传送路线。晴天消耗 x_i 为 i 的正因数之和加 x_{i-1} 后对 m 取模后再加一，雨天消耗 y_i 为 i 的不大于 m 的所有正倍数之和加 y_{i-1} 后对 m 取模后再加一。其中 u_0=v_0=x_0=y_0=0 ，注意 1 是所有数的因数；所有数的因数和倍数包含其自身。求到传送点 n 的最小消耗。
假设你的程序生成的数据前五条传送路径如下所示，那么你的数据生成可能是正确的：
| 起点 | 终点 | 是否双向 | 晴天消耗 | 雨天消耗 |
|---|---|---|---|---|
| 1400 | 1428 | Y | 2 | 2049 |
| 1218 | 42 | N | 6 | 2 |
| 199 | 238 | Y | 11 | 3416 |
| 195 | 442 | N | 19 | 1369 |
| 1151 | 1120 | Y | 26 | 960 |
输入
无
输出
你的答案