Minimum Time in Wormhole Network

Determine the minimum time required to travel from a starting point to a destination point in a two-dimensional coordinate system, considering both direct movement and the use of wormholes.

Explanation:

You are given a starting point (sx, sy) and a destination point (dx, dy). The spacecraft can move only in the X (left or right) or Y (up or down) direction. The time taken to move from one point (x1, y1) to another point (x2, y2) is calculated as |x2 - x1| + |y2 - y1| seconds.

Additionally, there are N wormholes in the system. Using a wormhole allows you to travel from its entry point to its exit point in a specified amount of time. Your task is to find the minimum time required to reach the destination, using direct movement and/or wormholes.

Input:

The first line contains 4 space-separated integers sx, sy, dx, and dy representing the source and destination points.
The second line contains an integer N, the number of wormholes.
Each of the next N lines contains five space-separated integers: the starting point (x1, y1), the exit point (x2, y2) of the wormhole, and the time taken to use the wormhole.

Output:

Print the minimum time required to travel from the source to the destination point.

Example:

Input:

sx = 0, sy = 0, dx = 10, dy = 10
N = 1
Wormhole: (2, 2) to (8, 8) with time 1

Output:

9

Explanation:

The optimal path may include using the wormhole if it reduces the total travel time.

Constraints:

• 1 <= Coordinates <= 10⁵
• 1 <= N <= 200
• 1 <= Wormhole Time <= 10⁵
• Time Limit: 1 sec