今天天气太好了,实验室的老师和同学们决定出去玩,给出起点s和目的地t,有n个地点,m条双向公交线路,每辆公交的价格可能不一样,同学们很穷但是时间充沛,所以他们决定花最少的钱去游玩,求出最少花费。
第一行两个数分别为n(2<=n<=105)、m(n-1<=m<=105)
第二行两个数分别为s,t(1<=s,t<=n)
接下来m行表示为辆公交的数据,格式如下:k cost u1 u2 u3 ... uk,代表有k(k<=20)个点,公交花费为cost(cost<=200),所有的k总和不超过3*105
一个数表示最少的花费。