Problem Statement

Wormhole Navigation A spaceship has to travel from a source point to a destination point on an infinite 2D integer grid. Flying directly between two points (x1, y1) and (x2, y2) costs abs(x1 - x2) + abs(y1 - y2) fuel. The galaxy also contains N wormholes. Wormhole i is described by five integers x1 y1 x2 y2 c : its two mouths are located at (x1, y1) and (x2, y2) , and entering one mouth and coming out of the other costs exactly c fuel, no matter how far apart the two mouths are. Every wormhole is bi-directional , so it may be traversed from (x1, y1) to (x2, y2) or from (x2, y2) to (x1, y1) , both at cost c . The spaceship may fly freely between any two points, may use any number of wormholes in any order, and may also use none of them at all. Determine the minimum total fuel needed to get from the source to the destination. Input Format The first line contains a single integer N , the number of wormholes. The second line contains four integers sx sy dx dy : the source is (sx, sy) and t