- 29

## Statement

## Goal

Difficulty: EasyTopic: A* algorithm, Pathfinding, Heuristic search

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

`start`to

`v`;

- the

`v`to the

`goal`and is given by the heuristic provided in input;

- the

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**three space-separated integers

`E`lines:`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 <

0 <

0 <

`N`< 1000 <

`E`< 100000 <

`C`< 1000Example

Input

3 3 0 2 33 11 0 0 1 10 0 2 40 1 2 20

Output

0 33 1 21 2 30

A higher resolution is required to access the IDE

Online Participants

### Channels

### Direct Messages

No private conversations