Dijkstra 算法是非常著名的贪心算法之一。

它用于解决单源最短路径问题，即指定一个特定源顶点，求该顶点到给定图的所有其他顶点的最短路径。

它由计算机科学家 Edsger W. Dijkstra 于 19561956 年构思并在三年后出版。

在该算法中，我们需要不断维护一个包含最短路径树中顶点的集合。

在每一步中，我们找到一个尚未在集合内且与源顶点距离最小的顶点，并将其收于集合中。

因此，通过 Dijkstra 算法，我们可以逐步生成一个有序的顶点序列，我们称之为 Dijkstra 序列。

对于一个给定的图，可能有多个 Dijkstra 序列。

例如，{5,1,3,4,2}{5,1,3,4,2} 和 {5,3,1,2,4}{5,3,1,2,4} 都是给定图的 Dijkstra 序列。

注意，序列中的第一个顶点即为指定的特定源顶点。

你的任务是检查给定的序列是否是 Dijkstra 序列。

第一行包含两个整数N和M，表示图中点和边的数量。

点的编号1∼N。

接下来M行，每行包含三个整数 a,b,c，表示点a和点b之间存在一条无向边，长度为 c。

再一行包含整数K，表示需要判断的序列个数。

接下来K行，每行包含一个 1∼N的排列，表示一个给定序列。

1≤N≤1000

1≤M≤10^5,

1≤a,b≤N,

1≤c≤100,

1≤K≤100,

保证给定无向图是连通图，

保证无重边和自环