405390: GYM101933 D Delivery Delays

Hannah recently discovered her passion for baking pizzas, and decided to open a pizzeria in downtown Stockholm. She did this with the help of her sister, Holly, who was tasked with delivering the pizzas. Their pizzeria is an instant hit with the locals, but, sadly, the pizzeria keeps losing money. Hannah blames the guarantee they put forth when they advertised the pizzeria:

"Do you have a craving for a delicious pizza? Do you want one right now? Order at Hannah's pizzeria and we will deliver the pizza to your door. If more than $$$20$$$ minutes elapse from the time you place your order until you receive your Hannah's pizza, the pizza will be free of charge!"

Even though Holly's delivery car can hold an arbitrary number of pizzas, she has not been able to keep up with the large number of orders placed, meaning they have had to give away a number of pizzas due to late deliveries.

Trying to figure out the best way to fix the situation, Hannah has now asked you to help her do some analysis of yesterday's orders. In particular, if Holly would have known the set of orders beforehand and used an optimal delivery strategy, what is the longest a customer would have had to wait from the time they placed their order until they received their pizza?

Hannah provides you with a map of the roads and road intersections of Stockholm. She also gives you the list of yesterday's orders: order $$$i$$$ was placed at time $$$s_i$$$ from road intersection $$$u_i$$$, and the pizza for this order was out of the oven and ready to be picked up for delivery at time $$$t_i$$$. Hannah is very strict about following the "first come, first served" principle: if order $$$i$$$ was placed before order $$$j$$$ (i.e. $$$s_i < s_j$$$), then the pizza for order $$$i$$$ will be out of the oven before the pizza for order $$$j$$$ (i.e. $$$t_i < t_j$$$), and the pizza for order $$$i$$$ must be delivered before the pizza for order $$$j$$$.

The first line of input contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 1\,000$$$, $$$1 \le m \le 5\,000$$$), where $$$n$$$ is the number of road intersections in Stockholm and $$$m$$$ is the number of roads. Then follow $$$m$$$ lines, the $$$i$$$'th of which contains three integers $$$u_i$$$, $$$v_i$$$ and $$$d_i$$$ denoting that there is a bidirectional road between intersections $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$), and it takes Holly's delivery car $$$d_i$$$ time units to cross this road in either direction ($$$0 \le d_i \le 10^8$$$). There is at most one road between any pair of intersections.

Then follows a line containing an integer $$$k$$$, the number of orders ($$$1 \le k \le 1\,000$$$). Then follow $$$k$$$ lines, the $$$i$$$'th of which contains three integers $$$s_i$$$, $$$u_i$$$, $$$t_i$$$ denoting that an order was made at time $$$s_i$$$ from road intersection $$$u_i$$$ ($$$2 \leq u_i \leq n$$$), and that the order is ready for delivery at time $$$t_i$$$ ($$$0 \le s_i \le t_i \le 10^8$$$). The orders are given in increasing order of when they were placed, i.e. $$$s_i < s_j$$$ and $$$t_i < t_j$$$ for all $$$1 \le i < j \le k$$$.

Hannah's pizzeria is located at road intersection $$$1$$$, and Holly and her delivery car are stationed at the pizzeria at time $$$0$$$. It is possible to reach any road intersection from the pizzeria.

Output a single integer denoting the longest time a customer has to wait from the time they place their order until the order is delivered, assuming that Holly uses a delivery schedule minimizing this value.

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

6

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

8

Explanation of the first sample:

 1-(2)-2
 |     |
(2)   (4)
 |     |
 4-(1)-3

3: take pizzas 1, 2
5: deliver pizza 1 (4)
6: deliver pizza 2 (3)
9: take pizza 3
11: deliver pizza 3 (7)

6: take pizzas 1,2,3
8: deliver pizza 1 (7)
9: deliver pizza 2,3 (6,5)

2: take pizza 1
4: deliver pizza 1 (3)
6: take pizza 2,3
9: deliver pizza 2,3 (6,5)