问题

从数据中心出来，外面的太阳已经升得很高了。

我真的很困。从凌晨2点左右开始的Nico Nico全面维护按计划在上午10点左右结束。虽然不算超时工作，但是我并不擅长调整生活节奏，因此在维护开始之前没有好好休息。我只想尽快回家躺在床上......但在此之前，我还担心能否安全地坐电车回家而不会睡过站。

有一个由N个车站和M条线路的电车网络。每条线路都可以在上下方向上行驶，并且一条线路不会在同一站停靠两次。

我想使用这个电车网络从车站src到达目的地dst。然而，当我乘坐电车并在线路的停靠站之间移动时，我可能随时会睡着。如果睡着了，我将错过原本要下车的站点，并继续乘坐到该方向的终点站。当我在终点站醒来后，我会感觉很清爽，所以在那之后我不会再错过乘车，我可以按照自己喜欢的路线移动到目的地。

麻烦的是，我在工作中喝了能量饮料，咖啡因还没有从体内排出。换句话说，我无法预测在移动过程中会在哪个时间睡着。

我希望能够选择最佳的移动路径，使得我在最糟糕的时机睡着时的最终移动时间最小。那么在这种情况下的移动时间是多少呢？

输入

输入以以下格式给出：

N M src dst L0 s0,0 s0,1 … s0,L0-1 w0,0 w0,1 … w0,L0-2 L1 s1,0 s1,1 … s1,L1-1 w1,0 w1,1 … w1,L1-2 :

第一行给出了N、M、src和dst（0≤src，dst<N），接下来的行给出了线路的信息。

每条线路的信息由3行组成。第一行给出了该线路包含的车站数Li。第二行按顺序给出了该线路的停靠站。第三行给出了表示站点之间移动所需时间的Li-1个整数，其中第j个数字表示该线路的第j个站到第j+1个站之间的所需时间（无论从哪个站到另一个站，所需时间都是相同的）。如果在从线路的第j个站到第j+1个站的移动过程中睡着了，那么将移动到车站Li-1；如果在从线路的第j+1个站到第j个站的移动过程中睡着了，那么将移动到车站0。请注意，可能有多条直接连接相同两个站的线路，而这种情况下不同线路的所需时间可能不同。

输入满足以下限制条件：

• 2≤N≤25,252
• 2≤Li （0≤i<M）
• L0+L1+...+LM-1≤252,525
• 1≤wi,j≤2,525
• src≠dst
• 源站和目的站之间至少存在一条路径。

部分分

根据数据集对输入进行评分，部分分总共50分，且满足以下限制：

• N≤252
• L0+L1+...+LM-1≤525
• wi,j≤25

输出

将问题中要求的移动时间输出为一行。不要忘记在输出末尾添加换行符。

示例1

5 2 0 3
3
0 1 2
1 2
3
1 3 4
1 1

输出示例1

6

由于可能在从站点0到站点1的过程中睡着，最佳路径是0-1-2-1-3，并且所需时间为6。

示例2

5 2 0 3
3
0 1 2
1 1
3
1 3 4
1 3

输出示例2

8

该示例与示例1具有相同的电车网络，但是站点之间的移动时间不同。因此，在0-1站之间睡着比在1-3站之间睡着所需时间更长。

请注意，无法控制在何时入睡。无论如何移动0-1-2站，都无法在这里睡觉。为了到达站点3，必须沿线1-3移动，并且在这里睡觉会导致更糟糕的结果。

示例3

4 2 0 1
3
0 1 2
1 3
3
0 3 1
1 1

输出示例3

2

使用第一条线路时，如果入睡，将被送到较远的地方。第二条线路的终点是目的地，无论在哪里入睡，都可以在2个时间单位内到达目的地。