有一个 个点 条边的有向带边权图，还有 条“禁止路径”。
一条禁止路径是一个点的序列，若图上的一条路径连续地经过了序列中的点，则称该路径包含了这条禁止路径。
一条从 到 的路径合法当且仅当其不包含任何禁止路径。
求每条合法路径的边权和的最小值。
，保证所有禁止路径的长度和 ，边权均非负。
对于所有禁止路径建立 AC 自动机，不难发现 AC 自动机上的每个点末尾的那个点是固定的，所以可以把原图的边直接迁移到 AC 自动机上。
直接做很慢，但是考虑瓶颈：
-
建 AC 自动机：开主席树快速复制 to 即可；
-
在 AC 自动机上跑 dijkstra：
不妨在建 AC 自动机的时候顺带记录每个 to 的边权。
不难发现 dij 的时候每次更新相当于是遍历的主席树上的一个子树。
根据 dij 的性质，若主席树上一个点之前已经被访问过了，则无需再访问，所以直接给主席树每个点开个 vis 即可；
时间复杂度 （认为所有东西都和 同阶），代码如下：
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
using namespace std;
template<typename T>
inline void read(T &x)
{
x=0;
T w=1;
char c=getchar();
while(c<'0'||c>'9') w=(c=='-'?-w:w),c=getchar();
while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
x*=w;
}
typedef long long ll;
const int S=200005,MS=S*3,TS=MS*20;
const ll inf=1e17;
int n,m,k,a[S];
map<int,ll> mp[S];
int cnt,ls[TS],rs[TS];
pair<int,ll> val[TS];
int tot,idx[MS];
map<int,ll> son[MS];
bool flg[MS];
int hed,til,que[MS],fail[MS],to[MS];
ll dis[MS];
bool vis[MS],del[TS];
priority_queue<pair<ll,int> > q;
void upd(int &u,int lst,int l,int r,int p,pair<int,ll> x)
{
u=++cnt;
val[u]=val[lst],ls[u]=ls[lst],rs[u]=rs[lst];
if(l==r) return val[u]=x,void();
int mid=l+r>>1;
if(p<=mid) upd(ls[u],ls[lst],l,mid,p,x);
else upd(rs[u],rs[lst],mid+1,r,p,x);
}
pair<int,ll> quet(int u,int l,int r,int p)
{
if(u==0) return make_pair(0,inf);
if(l==r) return val[u];
int mid=l+r>>1;
if(p<=mid) return quet(ls[u],l,mid,p);
else return quet(rs[u],mid+1,r,p);
}
inline void stx(int &u,int p,pair<int,ll> x){upd(u,u,1,n,p,x);}
inline pair<int,ll> qux(int u,int p){return quet(u,1,n,p);}
inline void ins(int len,bool f)
{
int u=0;
for(int i=1;i<=len;i++)
{
if(!son[u].count(a[i]))
{
son[u][a[i]]=++tot;
// printf("%d %d %d\n",u,tot,a[i]);
idx[tot]=a[i];
}
u=son[u][a[i]];
}
flg[u]=f;
}
inline ll getd(int x,int y)
{
if(!mp[x].count(y)) return inf;
return mp[x][y];
}
inline void build()
{
fail[0]=-1;
hed=1,til=0;
for(auto t:son[0])
{
int v=t.second,id=idx[v];
fail[v]=0;
flg[v]|=flg[fail[v]];
stx(to[0],id,make_pair(v,inf));
que[++til]=v;
}
while(hed<=til)
{
int u=que[hed++];
to[u]=to[fail[u]];
for(auto t:son[u])
{
int v=t.second,id=idx[v];
fail[v]=qux(to[fail[u]],id).first;
flg[v]|=flg[fail[v]];
// printf(">> %d %d\n",u,v);
if(!flg[v])
{
stx(to[u],id,make_pair(v,getd(idx[u],id)));
}
else
{
stx(to[u],id,make_pair(v,inf));
}
que[++til]=v;
}
}
}
void dfs(int u,int l,int r,ll d)
{
if(u==0||del[u]) return;
del[u]=true;
if(l==r)
{
int v=val[u].first;
ll w=val[u].second;
if(d+w<dis[v])
{
dis[v]=d+w;
q.emplace(-dis[v],v);
}
return;
}
int mid=l+r>>1;
dfs(ls[u],l,mid,d),dfs(rs[u],mid+1,r,d);
}
int main()
{
freopen("path.in","r",stdin);
freopen("path.out","w",stdout);
read(n),read(m),read(k);
for(int i=1;i<=m;i++)
{
int x,y;
ll w;
read(x),read(y),read(w);
mp[x][y]=w;
a[1]=x,a[2]=y;
ins(2,false);
}
for(int i=1;i<=k;i++)
{
int len;
read(len);
for(int j=1;j<=len;j++) read(a[j]);
ins(len,true);
}
build();
// for(int i=1;i<=tot;i++)
// {
// printf("%d(%d) %d\n",i,flg[i],fail[i]);
// }
// puts("------");
// for(int i=0;i<=tot;i++)
// {
// for(int j=1;j<=n;j++)
// {
// if(qux(to[i],j).second!=inf)
// printf("%d %d %lld\n",
// i,
// qux(to[i],j).first,
// qux(to[i],j).second);
// }
// }
for(int i=0;i<=tot;i++) dis[i]=inf;
if(!son[0].count(1)) return puts("-1"),0;
int srt=son[0][1];
if(flg[srt]) return puts("-1"),0;
// printf("srt: %d\n",srt);
dis[srt]=0;
q.emplace(-dis[srt],srt);
while(!q.empty())
{
int u=q.top().second;
q.pop();
if(vis[u]) continue;
vis[u]=true;
dfs(to[u],1,n,dis[u]);
}
ll ans=inf;
for(int i=1;i<=tot;i++) if(idx[i]==n) ans=min(ans,dis[i]);
// for(int i=0;i<=tot;i++)
// printf("%d(%d) %lld\n",i,idx[i],dis[i]);
printf("%lld\n",ans==inf?-1:ans);
return 0;
}