题目描述

一只兔子和一只乌龟决定赛跑。由于乌龟来自 Craiova 而兔子来自 Ardeal，乌龟比兔子跑得快的多。我们的目标是帮助兔子赢得比赛。

比赛在一个 $N$ 个点 $M$ 条边的图上进行，比赛在点 $1$ 开始，点 $N$ 结束。比赛前，兔子和乌龟都要先选出一条比赛时他们各自使用的路径。因此，他们知道这个图的情况和经过图上每条边的时间。

乌龟可能跑的比兔子快，但他还是一只乌龟（后文叫做 George）。George 会在他的路径上选出一些点来睡一会。如果某一时刻他知道了兔子在作弊，George 就不再睡觉，直到完成比赛。

兔子（后文叫做 Stan）只有一个优势，他的一个祖祖祖……祖母是一只狐狸，因此他也有狡猾的一面。Stan 并不打算按照他选好的路径来比赛（但 George 会按照路径比赛）。他计划在某一点更改路线，直接通过最短路径到达点 $N$。唯一的问题是他必须做出明智的选择，因为 George 一旦发现 Stan 在作弊，就会不再睡觉，这是不利的。

Stan 只能在到达一个点后更改路线（还在边上移动的时候是不能更改的）。他并不知道 George 的休息计划，但你知道！计算出 Stan 可以更改路线并赢得比赛的时间点数量。当 Stan 开始作弊的时候，George 只要没有在睡觉，就会立即察觉到。如果那时 George 在睡觉，则他醒来的时候才会察觉。

输入格式

第一行包含两个整数 $N$ 和 $M$。接下来 $M$ 行用 $(A,B,T,R)$ 的格式来描述图中的边：有一条边连接点 $A$ 和 $B$，乌龟经过这条边需要花费 $T$ 时间，兔子需要花费 $R$ 时间。边按输入顺序从 $1$ 到 $M$ 编号。

接下来一行包含一个整数 $P_T$，代表 George 路径上的边数。接下来 $P_T$ 行用 (边的编号, 睡眠时间) 来描述路径上的边：路径上有一条给定编号的边，在经过这条边后，George 会睡一会，睡眠时间给定。最后一条边的睡眠时间是没有意义的，因为 George 已经到终点了。

接下来一行包含一个整数 $P_R$，代表 Stan 最开始选择的路径上的边数。最后一行包含 $P_R$ 个整数，代表 Stan 最开始路径上的边的编号。

输出格式

输出第一行包含一个整数 $x$，代表 Stan 可以开始作弊的时间点（也就是开始作弊所在的点）数量。第二行包含 $x$ 个递增顺序的整数，代表 Stan 可以开始作弊的点的编号。

8 12
1 2 2 10
2 3 1 10
3 8 2 10
1 4 10 3
4 5 10 2
5 6 10 4
6 8 10 2
1 7 10 5
4 7 10 2
5 7 10 2
6 7 10 1
7 8 10 1
3
1 3
2 2
3 0
4
4 5 6 7

2
4 5

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

0

提示

• $2 \leq N \leq 100,000$
• $1 \leq P_R, P_T < 100,000$
• $1 \leq M \leq 200,000$
• $1 \leq T,R \leq 1,000,000,000$
• $0 \leq$ 睡眠时间 $\leq 1,000,000,000$
• 数据保证按照正确的顺序描述比赛路径上的边（即相邻两条边终点、起点相同）。
• 数据保证乌龟路径上的点不重复。
• 数据保证兔子路径上的点不重复。
• 如果兔子和乌龟同时到达终点，认为兔子赢了。
• 如果兔子在乌龟开始睡觉的时候开始作弊，那么乌龟会睡着，醒来时才察觉兔子在作弊。
• 认为兔子在作弊当且仅当他改变了路径且新路径严格快于原来的路径（否则就没必要作弊了）。
• 作弊路径可能与原始路径有相同的点。唯一的要求是在开始作弊的时候，兔子前往和原路径不同的点。在某些情况中，他也可能会回到之前经过的点。