Byteotheus 是 Byteotian 最著名的英雄，他再次从战斗中凯旋。当船员们正在装载战利品时，Byteotheus 在船舱里规划着回到家乡岛屿——Bitaca 的路线。这并非易事。许多神灵嫉妒 Byteotheus 在民众中的声望，很乐意挫挫他的锐气。幸运的是，其中一些神灵对他青睐有加，特别是女神 Bythena。正是她在昨晚托梦给 Byteotheus，警告他可能遇到的危险。

Byteonian 海上有 $n$ 个岛屿。为了方便起见，我们将它们编号为 $1$ 到 $n$。目前 Byteotheus 的船在岛屿 $1$，目的地是 Bitaca——岛屿 $n$。在某些情况下，两个岛屿之间有单向海路相连，此外每个岛屿最多是 $10$ 条海路的起点。我们将海路编号为 $1$ 到 $m$；第 $i$ 条路线从岛屿 $a_i$ 通往岛屿 $b_i$，航行需要花费恰好 $d_i$ 天。如果船在第 $t$ 天黎明从岛屿 $a_i$ 出发，沿第 $i$ 条路线航行，它将在第 $t + d_i$ 天的黎明到达目的地岛屿 $b_i$。船可以在任何岛屿停留任意长的时间，然后再继续航行。然而，在到达下一个岛屿之前，它不能偏离既定路径，也不能在航行中途停留超过完成该路线所需的时间。Byteotheus 最早可以在第 $1$ 天的黎明从岛屿 $1$ 出发。

女神 Bythena 的警告非常精确。她为 Byteotheus 提供了一份由众神准备的精确陷阱清单。每个陷阱都位于某个岛屿上，并在特定的时间段内处于激活状态。更准确地说，第 $i$ 个陷阱位于岛屿 $w_i$ 上，从第 $s_i$ 天开始到第 $k_i$ 天（含）处于激活状态。陷阱非常危险——如果 Byteotheus 的船发现自己处于一个有激活陷阱的岛屿上，船上的人将无一幸免。幸运的是，他的家乡 Bitaca 没有陷阱，且岛屿 $1$ 在第 $1$ 天也没有激活的陷阱。

显然，Byteotheus 希望规划回家的路线以避开所有陷阱。然而，他想知道由于这些陷阱，他需要多花多少时间。请帮助他，并指出安全返回 Bitaca 所需的最少天数。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 100\,000, 1 \le m \le 1\,000\,000$)：岛屿的数量和海路的数量。接下来的 $m$ 行描述海路：第 $i$ 行包含三个整数 $a_i, b_i, d_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i, 1 \le d_i \le 10^9$)，表示第 $i$ 条路线从岛屿 $a_i$ 通往岛屿 $b_i$，耗时 $d_i$ 天。所有路线均为单向。每个岛屿最多是 $10$ 条海路的起点。

下一行包含整数 $p$ ($0 \le p \le 100\,000$)，描述陷阱的数量。接下来的 $p$ 行包含陷阱的描述：第 $i$ 行包含三个整数 $w_i, s_i, k_i$ ($1 \le w_i \le n, 1 \le s_i \le k_i \le 10^9$)，表示第 $i$ 个陷阱位于岛屿 $w_i$，从第 $s_i$ 天开始到第 $k_i$ 天（含）处于激活状态。如果 $w_i = 1$，则 $s_i > 1$。

输出格式

如果无法规划出避开所有陷阱的路线，则仅输出一行单词 NIE（波兰语中的“不”）。否则，输出一个整数 $d$，描述完成航行所需的最少天数（船在第 $d+1$ 天的黎明到达 Bitaca）。

样例

输入 1

5 6
1 2 3
1 4 13
2 3 1
2 4 2
3 2 2
4 5 1
5
1 2 4
1 8 8
2 6 7
2 10 11
4 6 7

输出 1

10

Byteotheus 在第 $1$ 天黎明从岛屿 $1$ 出发。他在第 $4$ 天到达岛屿 $2$。他在那里等待了一天，然后出发前往岛屿 $3$。在第 $6$ 天到达那里后，他立即折返前往岛屿 $2$，并于第 $8$ 天从那里出发前往岛屿 $4$。他在第 $10$ 天到达那里，并最终在第 $11$ 天到达 Bitaca。