Hannah 最近发现了她对烘焙披萨的热情，并决定在斯德哥尔摩市中心开一家披萨店。在她的妹妹 Holly 的帮助下，她开始了披萨配送业务。他们的披萨店在当地很受欢迎，但遗憾的是，披萨店一直在亏损。Hannah 将此归咎于他们在宣传披萨店时做出的保证：

Picture by Clker-Free-Vector-Images via Pixabay, CC0

您渴望吃到美味的披萨吗？您现在就想吃吗？在 Hannah 的披萨店下单，我们将把披萨送到您的门口。如果您下单后超过 20 分钟还没收到 Hannah 的披萨，披萨将免费赠送！

尽管 Holly 的送货车可以容纳任意数量的披萨，但她一直无法跟上大量的订单，这意味着由于配送延迟，他们不得不送出许多免费披萨。

为了找出解决这一困境的最佳方法，Hannah 现在请你帮她分析昨天的订单。具体来说，如果 Holly 事先知道所有订单并采用了最优的配送策略，那么顾客从下单到收到披萨所等待的最长时间是多少？

Hannah 为你提供了斯德哥尔摩的道路和路口地图。她还提供了昨天的订单列表：订单 $i$ 是在时间 $s_i$ 从路口 $u_i$ 下达的，该订单的披萨在时间 $t_i$ 出炉并准备好配送。Hannah 非常严格地遵循“先到先得”原则：如果订单 $i$ 在订单 $j$ 之前下达（即 $s_i < s_j$），那么订单 $i$ 的披萨将比订单 $j$ 的披萨先出炉（即 $t_i < t_j$），并且订单 $i$ 的披萨必须在订单 $j$ 的披萨之前送达。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 1000, 1 \le m \le 5000$)，其中 $n$ 是斯德哥尔摩的路口数量，$m$ 是道路数量。接下来 $m$ 行，第 $i$ 行包含三个整数 $u_i, v_i$ 和 $d_i$，表示路口 $u_i$ 和 $v_i$ 之间有一条双向道路（$1 \le u_i, v_i \le n, u_i \neq v_i$），Holly 的送货车在任一方向上通过这条路需要 $d_i$ 个时间单位（$0 \le d_i \le 10^8$）。任意两个路口之间最多只有一条道路。

接下来一行包含一个整数 $k$，表示订单数量（$1 \le k \le 1000$）。接下来 $k$ 行，第 $i$ 行包含三个整数 $s_i, u_i, t_i$，表示订单是在时间 $s_i$ 从路口 $u_i$ 下达的（$2 \le u_i \le n$），且该订单在时间 $t_i$ 准备好配送（$0 \le s_i \le t_i \le 10^8$）。订单按下单时间递增的顺序给出，即对于所有 $1 \le i < j \le k$，满足 $s_i < s_j$ 且 $t_i < t_j$。

Hannah 的披萨店位于路口 1，Holly 和她的送货车在时间 0 时位于披萨店。从披萨店可以到达任何路口。

输出格式

输出一个整数，表示在 Holly 采用最小化该值的配送策略下，顾客从下单到收到披萨所等待的最长时间。

样例

输入格式 1

4 4
1 2 2
2 3 4
3 4 1
4 1 2
3
1 4 2
3 3 3
4 3 6

输出格式 1

6

输入格式 2

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

输出格式 2

8