题目描述

Hannah 最近迷上了烤披萨，并在斯德哥尔摩市中心开了一家披萨店。她的妹妹 Holly 负责配送披萨。

披萨店很快大受欢迎，但遗憾的是，店里一直在亏钱。Hannah 认为原因在于她们打广告时做出的承诺：

想吃美味披萨吗？现在就想吃吗？来 Hannah 披萨店下单吧！我们会把披萨送到你家门口。若从你下单开始到收到披萨超过 20 分钟，这份披萨免费！

虽然 Holly 的送餐车可以装任意多份披萨，但订单数量实在太多，她没能及时配送，导致店里送出了不少免费披萨。

现在 Hannah 想分析昨天的订单。假设 Holly 事先知道所有订单，并采用最优配送策略，那么顾客从下单到收到披萨的最长等待时间最小可以是多少？

Hannah 给你一张斯德哥尔摩道路图，以及昨天的订单列表。第 $i$ 个订单满足：

• 顾客在时间 $s_i$ 从路口 $u_i$ 下单；
• 该订单对应的披萨在时间 $t_i$ 出炉，可以被取走配送。

Hannah 非常严格地遵守“先来先服务”原则：如果订单 $i$ 的下单时间早于订单 $j$，即 $s_i<s_j$，那么订单 $i$ 的披萨也会更早出炉，即 $t_i<t_j$，并且订单 $i$ 必须先于订单 $j$ 被送达。

披萨店位于路口 $1$，Holly 和她的车在时间 $0$ 时也位于披萨店。

输入格式

第一行包含两个整数 $n,m$：

• $n$ 表示道路交叉口数量；
• $m$ 表示道路数量。

满足：

$$2\le n\le 1000, \qquad 1\le m\le 5000.$$

接下来 $m$ 行，第 $i$ 行包含三个整数 $u_i,v_i,d_i$，表示路口 $u_i$ 和 $v_i$ 之间有一条双向道路，Holly 的车经过这条路需要 $d_i$ 个时间单位。

满足：

$$1\le u_i,v_i\le n, \qquad u_i\ne v_i, \qquad 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$ 下单；
• 该订单在时间 $t_i$ 出炉，可以配送。

满足：

$$2\le u_i\le n, \qquad 0\le s_i\le t_i\le 10^8.$$

订单按下单时间递增给出，即对于所有 $1\le i<j\le k$，都有：

$$s_i<s_j, \qquad t_i<t_j.$$

保证从披萨店所在的路口 $1$ 可以到达任意路口。

输出格式

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

输入输出样例 #1

输入 #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

输入 #2

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

输出 #2

8