ADP is a cute caterpillar living in the SK (Shik Kingdom). According to the tradition, every caterpillar in SK must go to the LAND once in the lifetime, hence ADP has just decided to make a journey. However, it's not that easy to go to the LAND, ADP will encounter birds, which will eat caterpillars, during the trip. Luckily, birds will only appear on roads between cities, so ADP can just stay in city for a while to wait for birds to fly away. ADP wrote a program to analyze the behavior of birds and find out when those birds will show up. Unfortunately, ADP is not familiar with Dijkstra
hence just can't write a program to figure out how much time this trip will takes. In order to accomplish her dream, she asks her smartest friend, you, to write the program. Can you help her?
There's only one integer T in the first line, representing the number of test cases. The first line of each test case contains two integers N, M, the number of cities and the number of roads. city0 is ADP's hometown and cityn-1 is the LAND. Each of the next M lines describes one road. There're at least four integers in each line, V1, V2, C, D, indicating that it's a bidirectional road between cityv1 , cityv2 and ADP will need C units of time to crawl through it. The next D integers T1, T2… TD in the line represents that birds will show up at this road at time T1, T2… TD. ADP will be eaten if she's still crawling on this road while birds show up. We guarantee that there's a path to get to the LAND.
1<=T<=10
1<=N, M, ΣD<=2*10^5
1<=C<=2000
0<=Ti<=2^31-1
Output the minimum units of time that ADP needs to get to the LAND for each test case.