You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【题目描述】

贝茜想到一个更温暖的地方去度过这个寒冷的冬天。不幸地是,她发现只有一家名叫AB的航空公司愿意把票卖给奶牛,而且这些票的构成有些奇怪。

AB拥有N架飞机,每架都有一个特定的飞行路线,这个飞行路线包含2个或更多的城市。例如,一架飞机的路线可能是从城市1开始，然后飞到城市5,再飞到城市2,最后飞到城市8。没有城市会在一条路线上出现多次。

如果贝茜决定使用这条路线，她可以在一条路线的任意一个城市上飞机，在最后一个城市下飞机。她不用一定在第一个城市上飞机,在最后一个城市下飞机。每条路线会有一个价格,不管贝茜沿途经过多少城市,她都要付这么多钱。

贝茜想找到最近的从城市A到城市B的距离。由于她不想被复杂的行程困惑,​她想只使用最多两条路线​，请帮她决定她最少应该付多少钱。

【输入格式】

第一行包含3个数字A、B、N。

下面的2N行，描述可用的路线，每条路线的描述占两行。第一行包含路线费用以及沿途有多少个城市（不超过500个），第二行包含一个按顺序的城市列表。

【输出格式】

输出贝茜从城市A飞到城市B的最小费用。如果没有这样的路线，输出-1。

【样例输入】

1 2 3

3 3

3 2 1

4 4

2 1 4 3

8 5

4 1 7 8 2

【样例输出】

7

【样例说明】

用路线2从城市1到城市3,再用路线1从城市3到城市2。

【数据规模】

对于20%的数据满足:N≤10

对于40%的数据满足:N≤100

对于100%的数据满足:N≤10000