For a given map with cities from Europe and distances between them, find the shortest path from Paris to Bucharest knowing that the direct distances between the cities are in the table. Use the following methods to address it and show your steps in search trees.

$(1)$ DFS $(15$ points$)$

$(2)$ BFS $(15$ points$)$

$(3)$ UCS $(15$ points$)$

$(4)$ A$*(25$ points$)$

Map of cities in Europe

City distances

Distance between Bucharest to any cities