加一个信仰优化就能AC，当遍历次数 $>5×10^7$ 直接输出 $-1$。

for(auto [v,w]:G[u]){
	tot++;
	if(d[v]>d[u]+w){
		d[v]=d[u]+w;
		dep[v]=dep[u]+1;
		if(!vis[v]) vis[v]=1,q.push(v);
	}
	if(tot>50000000) return !(cout<<-1);
	if(dep[v]>n+1) return !(cout<<-1);
}