Suppose you implemented Dijkstra's algorithm using a priority queue which supports each operations with the following worst-case performance, where n is the number of items in the priority queue:search: O(1)insert: O(loglog(n))delete: O(1)extractMin: O(loglog(n))decreaseKey: O(sqrt(n))isEmpty: O(1)You are given a connected, directed, weighted graph G with non-negative weights and a specified source.  G has n nodes and m edges.  What is the running time of Dijkstra's Algorithm on G using this new priority queue?  (There are no other changes made to Dijkstra's Algorithm.)

The running time of Dijkstra's Algorithm using this new priority queue can be calculated by considering the operations that the algorithm performs and their respective time complexities.

1. Initialization: This involves inserting all the nodes into the priority queue. Since there are n nodes and the time complexity of insert operation is O(loglog(n)), this step will take O(nloglog(n)) time.

2. Extracting the minimum: This operation is performed n times (once for each node) and the time complexity of extractMin operation is O(loglog(n)). So, this step will take O(nloglog(n)) time.

3. Updating the distances: This involves decreasing the key in the priority queue. In the worst case, this operation can be performed for every edge. Since there are m edges and the time complexity of decreaseKey operation is O(sqrt(n)), this step will take O(m*sqrt(n)) time.

4. Checking if the priority queue is empty: This operation is performed n times (once for each node) and the time complexity of isEmpty operation is O(1). So, this step will take O(n) time.

Adding up all these, the total running time of Dijkstra's Algorithm using this new priority queue is O(nloglog(n) + nloglog(n) + msqrt(n) + n) = O(msqrt(n) + 2nloglog(n) + n).

So, the running time of Dijkstra's Algorithm on G using this new priority queue is O(m*sqrt(n) + 2nloglog(n) + n).