[SGU503] Running City

题目描述

给定一张有向带权图。你需要从起点 $S$ 跑到终点 $T$，第 $i$ 条边有基础耗时 $c_i$。

除此之外，还有若干条“特殊路线”。每条特殊路线由一串边编号组成，并保证这些边构成一条不重复经过顶点的合法有向简单路径。

如果你的实际行走路径中，完整连续地经过了某条特殊路线，那么在走完这条特殊路线时会额外损失一段时间，额外耗时恰好等于该特殊路线所有边的基础耗时之和。换句话说，这一段相当于被计算了两次。

若路径中同时出现多条特殊路线，则每一次出现都要分别计算额外耗时。输入中甚至可以出现完全相同的特殊路线，此时它们的惩罚会叠加。

求从 $S$ 到 $T$ 的最小总耗时。

输入格式

第一行五个整数 $n,m,r,S,T$：

• $2\le n\le1000$；
• $0\le m\le10000$；
• $0\le r\le1000$；
• $1\le S,T\le n$ 且 $S\ne T$。

接下来 $m$ 行，每行三个整数 $a,b,c$，表示一条从 $a$ 指向 $b$、耗时为 $c$ 的有向边，其中 $1\le a,b\le n$、$a\ne b$、$1\le c\le1000$。每个顶点的出度不超过 $10$。边按输入顺序编号为 $1\sim m$。

接下来 $r$ 行描述特殊路线。每行先给出整数 $k$，随后给出 $k$ 个边编号。每条路线都是合法简单路径。

额外保证：

• 所有特殊路线长度之和不超过 $2m$；
• 每条边至多出现在 $10$ 条特殊路线中。

输出格式

若无法从 $S$ 到达 $T$，输出一行 -1。

否则输出一行一个整数，表示从 $S$ 到 $T$ 的最小总耗时。

样例 1

样例输入

3 3 1 1 3
1 2 2
2 3 1
1 3 2
1 3

样例输出

3