RT，除了#1全WA了，手写 zkw线段树 优化 Dij/kk

#include<cstdio>
const int M=3e3+5;
int n,m,G,d[M],ans[M],vis[M],zkw[M<<2];
struct Edge{
	int to,val;Edge*nx;
}e[M*70],to[M*70],*hd[M],*h[M],*cnt=e,*tot=to;
inline int max(const int&a,const int&b){
	return a>b?a:b;
}
inline void Add(const int&u,const int&v,const int&val){
	*cnt=(Edge){v,val,h[u]};h[u]=cnt++;
}
inline void Link(const int&u,const int&v){
	*tot=(Edge){v,0,hd[u]};hd[u]=tot++;
}
inline void Modify(register int u,const int&val){
	for(u+=G,u>>=1;u;u>>=1)zkw[u]=zkw[u<<1|(d[zkw[u<<1]]>d[zkw[u<<1|1]])];
}
signed main(){
	register int i,u,v,dis,val;
	register Edge*E;
	scanf("%d%d",&n,&m);
	for(G=1;G<n;G<<=1);
	for(i=0;i<=n;++i)d[zkw[i+G]=i]=2e9;
	Modify(1,d[1]=0);
	for(i=1;i<=m;++i){
	    scanf("%d%d%d",&u,&v,&val);
	    Add(u,v,val);
	}
	for(i=1;i<=n;++i){
		scanf("%d",&dis);vis[i]=dis;
		while(dis--){
			scanf("%d",&v);
			Link(v,i);
		}
	}
	for(i=1;i<=n;++i){
		vis[u=zkw[1]]=-1;
		dis=ans[u]=max(d[u],ans[u]);
		Modify(u,d[u]=2e9);
		for(E=h[u];E;E=E->nx){
		    v=E->to;val=E->val;
    		if(dis+val<d[v]){
    			d[v]=dis+val;
    		    if(!vis[v])Modify(v,max(d[v],ans[v]));
    		}
		}
		for(E=hd[u];E;E=E->nx){
			v=E->to;
			ans[v]=max(ans[v],dis);
			if(!--vis[v])Modify(v,d[v]=max(d[v],ans[v]));
		}
	}
	printf("%d",ans[n]);
}