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 #cf_span(class=[tex-font-style-underline], body=[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 <= n <= 1 thin 000$, $1 <= m <= 5 thin 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 <= u_i, v_i <= n$, $u_i eq.not v_i$), and it takes Holly's delivery car $d_i$ time units to cross this road in either direction ($0 <= d_i <= 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 <= k <= 1 thin 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 <= u_i <= n$), and that the order is ready for delivery at time $t_i$ ($0 <= s_i <= t_i <= 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 <= i < j <= 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.
Explanation of the first sample:
## Input
The first line of input contains two integers $n$ and $m$ ($2 <= n <= 1 thin 000$, $1 <= m <= 5 thin 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 <= u_i, v_i <= n$, $u_i eq.not v_i$), and it takes Holly's delivery car $d_i$ time units to cross this road in either direction ($0 <= d_i <= 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 <= k <= 1 thin 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 <= u_i <= n$), and that the order is ready for delivery at time $t_i$ ($0 <= s_i <= t_i <= 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 <= i < j <= 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
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.
[samples]
## Note
Explanation of the first sample: 1-(2)-2 | |(2) (4) | | 4-(1)-33: take pizzas 1, 25: deliver pizza 1 (4)6: deliver pizza 2 (3)9: take pizza 311: deliver pizza 3 (7)6: take pizzas 1,2,38: deliver pizza 1 (7)9: deliver pizza 2,3 (6,5)2: take pizza 14: deliver pizza 1 (3)6: take pizza 2,39: deliver pizza 2,3 (6,5)
**Definitions**
Let $ G = (V, E) $ be an undirected weighted graph with $ n $ vertices (road intersections) and $ m $ edges (roads), where each edge $ (u, v) \in E $ has weight $ d \in \mathbb{R}_{\geq 0} $ representing travel time.
Let $ p \in V $ denote the pizzeria location: $ p = 1 $.
Let $ k \in \mathbb{Z}^+ $ be the number of orders.
For each order $ i \in \{1, \dots, k\} $:
- $ s_i \in \mathbb{R}_{\geq 0} $: time when order was placed,
- $ u_i \in V \setminus \{1\} $: delivery location,
- $ t_i \in \mathbb{R}_{\geq 0} $: time when pizza is ready (with $ s_i \leq t_i $).
Orders are indexed in increasing order of placement: $ s_1 < s_2 < \dots < s_k $, and hence $ t_1 < t_2 < \dots < t_k $.
Let $ \delta(u, v) $ denote the shortest-path distance between vertices $ u $ and $ v $ in $ G $.
Holly starts at vertex $ 1 $ at time $ 0 $. She must deliver orders in order $ 1 $ to $ k $, and for order $ i $:
- She cannot leave for delivery before time $ t_i $,
- She must pick up pizza $ i $ at time $ \geq t_i $,
- She must deliver it to $ u_i $, arriving at time $ \geq t_i + \delta(1, u_i) $ if starting from pizzeria, but may come from previous delivery location.
**Constraints**
1. $ 2 \leq n \leq 1000 $, $ 1 \leq m \leq 5000 $
2. $ 1 \leq k \leq 1000 $
3. $ 0 \leq d_i \leq 10^8 $, $ 0 \leq s_i \leq t_i \leq 10^8 $
4. The graph is connected.
5. Delivery sequence must respect order: order $ i $ must be delivered before order $ j $ for all $ i < j $.
**Objective**
Find the minimum possible value of the maximum wait time over all customers:
$$
\min_{\text{delivery schedule } \sigma} \max_{i \in \{1,\dots,k\}} \left( \text{delivery time of order } i - s_i \right)
$$
where $ \sigma $ is a sequence of departure times and paths satisfying:
- Holly starts at vertex $ 1 $ at time $ 0 $,
- For each $ i $, delivery of order $ i $ occurs at time $ \geq t_i $,
- Travel time between delivery locations follows $ \delta(\cdot, \cdot) $,
- Orders are delivered in order $ 1, 2, \dots, k $.
Output: This minimal maximum wait time.