Apply the Uniform Cost Search algorithm to the graph given below, where S is the start state and G$1,$G$2$ and G$3$ are the goal states.

Show the sorted list at every step of the algorithm and also show at every step, the solution state space as it grows.

Finally, clearly indicate the path cost from the start node to the goal node and the path taken within the solution tree.