Goal
You are given an undirected graph with weighted edges, a start and a goal node, and for each node the heuristic value, which is the estimated distance to the end. Your task is to trace a canonical A* execution (see https://en.wikipedia.org/wiki/A*_search_algorithm ) by computing a shortest path from the start to the goal.
We recall that the A* algorithm will rely on three values for each node v:
- the g-value, which is the minimum distance from the start to v;
- the h-value, which is an estimation of the minimum distance from v to the goal and is given by the heuristic provided in input;
- the f-value, which is the sum of the g-value and h-value.
There is always a path between the start and the goal. The given heuristic is admissible and consistent, meaning that the A* algorithm will always find a shortest path from the start to the goal.
When some nodes have the same f-value, the one with the smaller identifier is considered first.
Input
Line 1: 4 space-separated integers:
N - the number of nodes in the graph (nodes are identified by integers from 0 to N-1),
E - the number of edges in the graph,
S - the identifier of the start node,
G - the identifier of the goal node
Line 2: N space-separated integers - estimated distances to the goal (heuristics) for each node from 0 to N-1
Next E lines: three space-separated integers X Y C that indicate the edge between nodes X and Y with the cost C. Notice that, since the graph is undirected, there is also an edge from Y to X with the same cost.
Output
A sequence of lines containing information about the node expanded in each step of the algorithm: the node's identifier, followed by a space, followed by its f-value.
Constraints
0 < N < 100
0 < E < 10000
0 < C < 1000
Example
Input
3 3 0 2
33 11 0
0 1 10
0 2 40
1 2 20
