The following table presents de distance between the connected cities.

Cities	1	2	3	4	5	6	7	8	9	10
1		30		75			45
2	30		12
3		12		13
4	75		13		14		23
5				14		12		25
6					12		15		40
7	45			23		15
8					25				39	30
9						40		39		77
10								30	77

Consider the problem of finding a path from city 1 to city 10, using the heuristic given below in the following table.

City	Heuristic
1	140
2	90
3	90
4	80
5	60
6	55
7	78
8	35
9	60
10	0

A) Apply the A* on the same problem. Show the details of exploration of the algorithm. (3 Marks)

B) Is the solution found by the A* optimal? Justify and explain.