首先由题意可以知道
1.你到达一个城市 若他有保护罩 你必须去保存保护罩发射器的地方去摧毁掉
2.他是有很多人可以同时进行
3.若你到达了一个地方 但是他的保护罩没有摧毁掉 你必须摧毁掉他的保护罩
才能算完全到达

由上面知道 首先这是一个拓扑图

然后只需要从能跑的地方一个一个跑接下来的地方即可

#include<iostream>
#include<cstring>
#include<vector>
#include<utility> 
#include<queue>
#define x first
#define y second

using namespace std;

const int N = 3100,M = 7e4 + 10;

typedef long long ll;

typedef pair<ll,int> PII;

int head[N],to[M];ll w[M];int last[M],cnt;
void add(int a,int b,ll c){
	to[++cnt] = b;
	w[cnt] = c;
	last[cnt] = head[a];
	head[a] = cnt;
}

vector<int>v[N];

int n,m;

ll dist[N];int flag[N],de[N];ll dt[N];
void dij(){
	memset(flag,0,sizeof flag);
	memset(dt,0,sizeof dt);
	priority_queue<PII,vector<PII>,greater<PII > > q;
	for(int i = 1; i <= n; i++){
		dist[i] = 1e18;
	}
	q.push({0,1});
	dist[1] = 0;
	while(q.size()){
		PII p = q.top();
		q.pop();
		if(flag[p.y]) continue;
		flag[p.y] = 1;
		for(auto i : v[p.y]){
			de[i]--;
			dt[i] = max(dt[i],dt[p.y]);
			if(de[i] == 0 && dist[i] != 1e18){
				dist[i] = max(dist[i],dt[i]); //如果他已经全部跑完了 跑过了并且已经是最短路了 他必须要比摧毁保护罩的时间大或者等于
				q.push({dist[i],i});
			}
		}
		for(int i = head[p.y]; i != -1; i = last[i]){
			int j = to[i];
			if(dist[j] > dist[p.y] + w[i]){
				dist[j] = max(dist[p.y] + w[i],dt[j]); //更新
				if(de[j] == 0) q.push({dist[j],j}); //如果没有跑完de[j]更新的话 后面的所有都是错误的 那更新会很麻烦
			}
		}
	}
}

int main(){
	int t;
	cin >> t;
	while(t--){
		memset(head,-1,sizeof head);
		memset(de,0,sizeof de);
		cnt = 0;
		scanf("%d%d",&n,&m);
		for(int i = 0; i <= n; i++){
			v[i].clear();
		}
		for(int i = 1; i <= m; i++){
			int x,y;ll z;
			scanf("%d%d%lld",&x,&y,&z);
			add(x,y,z);
		}
		
		for(int i = 1; i <= n; i++){
			int x,y;
			scanf("%d",&x);
			for(int j = 1; j <= x; j++){
				scanf("%d",&y);
				v[y].push_back(i);
				de[i]++;
			}
		}
		
		dij();
		
		cout << dist[n] << endl; 
		
	}
	
	
	
	
	
	return 0;
}