【Planets】【CodeForces - 230D】（spfa+二分）

题目：

Goa\'uld Apophis captured Jack O\'Neill\'s team again! Jack himself was able to escape, but by that time Apophis\'s ship had already jumped to hyperspace. But Jack knows on what planet will Apophis land. In order to save his friends, Jack must repeatedly go through stargates to get to this planet.

Overall the galaxy has n planets, indexed with numbers from 1 to n. Jack is on the planet with index 1, and Apophis will land on the planet with index n. Jack can move between some pairs of planets through stargates (he can move in both directions); the transfer takes a positive, and, perhaps, for different pairs of planets unequal number of seconds. Jack begins his journey at time 0.

It can be that other travellers are arriving to the planet where Jack is currently located. In this case, Jack has to wait for exactly 1 second before he can use the stargate. That is, if at time t another traveller arrives to the planet, Jack can only pass through the stargate at time t + 1, unless there are more travellers arriving at time t + 1 to the same planet.

Knowing the information about travel times between the planets, and the times when Jack would not be able to use the stargate on particular planets, determine the minimum time in which he can get to the planet with index n.

Input

The first line contains two space-separated integers: n (2 ≤ n ≤ 105), the number of planets in the galaxy, and m (0 ≤ m ≤ 105) — the number of pairs of planets between which Jack can travel using stargates. Then m lines follow, containing three integers each: the i-th line contains numbers of planets ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi), which are connected through stargates, and the integer transfer time (in seconds) ci (1 ≤ ci ≤ 104) between these planets. It is guaranteed that between any pair of planets there is at most one stargate connection.

Then n lines follow: the i-th line contains an integer ki (0 ≤ ki ≤ 105) that denotes the number of moments of time when other travellers arrive to the planet with index i. Then ki distinct space-separated integers tij (0 ≤ tij < 109) follow, sorted in ascending order. An integer tij means that at time tij (in seconds) another traveller arrives to the planet i. It is guaranteed that the sum of all ki does not exceed 105.

Output

Print a single number — the least amount of time Jack needs to get from planet 1 to planet n. If Jack can\'t get to planet n in any amount of time, print number -1.

Examples

Input

4 6
1 2 2
1 3 3
1 4 8
2 3 4
2 4 5
3 4 3
0
1 3
2 3 4
0

Output

7

Input

3 1
1 2 3
0
1 3
0

Output

-1

Note

In the first sample Jack has three ways to go from planet 1. If he moves to planet 4 at once, he spends 8 seconds. If he transfers to planet 3, he spends 3 seconds, but as other travellers arrive to planet 3 at time 3 and 4, he can travel to planet 4 only at time 5, thus spending 8 seconds in total. But if Jack moves to planet 2, and then — to planet 4, then he spends a total of only 2 + 5 = 7 seconds.

In the second sample one can\'t get from planet 1 to planet 3 by moving through stargates.

解题报告：当时看到这个题目就是觉得非常的困难，然后又因为要考四级，所以就没有去做，后来学长讲课的时候讲了一下这道题目，觉得思路很奇妙，只依据最短路的基础上增加了时间的预处理，只要是将这个结点在某个时间是不能使用的进行预处理一下，每个时间是不是能够正常使用的，或者是在多久之后是可以进行正常使用的，参考了学长的代码，利用了vector并且进行了二分，觉得这个题真的很棒！（注释在代码中了）！

ac代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int inf=0x3f3f3f3f;
const int maxn=1e5+1000;

struct node{
	int v;
	int w;
	int next;
}; 

vector<int > pre[maxn],nxt[maxn];
queue<int > que;
node edge[maxn*2];
int head[maxn],dis[maxn],mk[maxn];
int n,m,cnt;

void addedge(int u,int v,int w)
{
	edge[cnt].v=v;
	edge[cnt].w=w;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}

int gettime(int u,int t)
{//处理特殊时间的函数 
	int l,r,mid;
	l=0;
	r=pre[u].size()-1;
	while(l<=r)
	{
		mid=(l+r)/2;
		if(pre[u][mid]<t)
			l=mid+1;
		else if(pre[u][mid]>t)
			r=mid-1;
		else
			return nxt[u][mid];//如果二分能够成功找到就返回咱们已经预处理过的可以正常使用的时间 
	}
	return t;//如果没有找到。就是可以直接正常使用的时间不需要等待！ 
}

int spfa()
{
	int i,u,v,w,res;
	memset(dis,inf,sizeof(dis));
	que.push(1);
	dis[1]=gettime(1,0);
	mk[1]=1;
	while(!que.empty())
	{
		u=que.front();
		que.pop();
		mk[u]=0;
		for(i=head[u];i!=-1;i=edge[i].next)
		{
			v=edge[i].v,w=edge[i].w;
			if(v==n) res=dis[u]+w;
			else res=gettime(v,dis[u]+w);
			if(dis[v]>res)
			{
				dis[v]=res;
				if(mk[v]==0)
				{
					que.push(v);
					mk[v]=1;
				}
			}
		}
	}
	return dis[n];
}

int main()
{
	int i,j,u,v,w,k,p,res;
	scanf(\"%d%d\",&n,&m);
	memset(head,-1,sizeof(head));
	cnt=0;
	for(i=1;i<=m;i++)
	{
		scanf(\"%d%d%d\",&u,&v,&w);
		addedge(u,v,w);
		addedge(v,u,w);
	}//前向星建图 
	for(i=1;i<=n;i++)
	{
		scanf(\"%d\",&k);
		while(k--)
		{//将该结点的使用时间存下来 
			scanf(\"%d\",&w);
			pre[i].push_back(w);
			nxt[i].push_back(w);
		}
		sort(pre[i].begin(),pre[i].end());//排序一下 
		for(j=pre[i].size()-1,p=-1;j>=0;j--)
		{
			if(p==-1||pre[i][j]+1!=pre[i][j+1])
				nxt[i][j]=pre[i][j]+1;
			else
				nxt[i][j]=p;
			p=nxt[i][j];
		}//将结点的使用时间进行一下预处理，如果使用这个结点之后没有继续被别的使用，那么就nxt是存放+1，如果不是的话，就存放之后能
		//正常使用的时间！！！ 
	}
	res=spfa();
	if(res==inf)
		printf(\"-1\\n\");
	else
		printf(\"%d\\n\",res);
	return 0;
}