集训队去旅游
题号:NC24303
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

今天天气太好了,实验室的老师和同学们决定出去玩,给出起点s和目的地t,有n个地点,m条双向公交线路,每辆公交的价格可能不一样,同学们很穷但是时间充沛,所以他们决定花最少的钱去游玩,求出最少花费。

输入描述:

第一行两个数分别为n(2<=n<=105)、m(n-1<=m<=105)

第二行两个数分别为s,t(1<=s,t<=n)

接下来m行表示为辆公交的数据,格式如下:k cost uuu... uk,代表有k(k<=20)个点,公交花费为cost(cost<=200),所有的k总和不超过3*105

输出描述:

一个数表示最少的花费。
示例1

输入

复制
11 4
1 10
5 1 1 2 3 4 5
4 2 8 7 2 6
3 2 8 9 10
3 10 10 4 11

输出

复制
5