Given a weighted, undirected and connected graph of V vertices and an adjacency list adj where adj[i] is a list of lists containing two integers where the first integer of each list j denotes there is edge between i and j , second integers corresponds to the weight of that  edge . You are given the source vertex S and You to Find the shortest distance of all the vertex's from the source vertex S. You have to return a list of integers denoting shortest distance between each node and Source vertex S.
 
Note: The Graph doesn't contain any negative weight cycle.
 
Example 1:
Input:
V = 2
adj [] = {{{1, 9}}, {{0, 9}}}
S = 0
Output:
0 9
Explanation:
The source vertex is 0. Hence, the shortest 
distance of node 0 is 0 and the shortest 
distance from node 1 is 9.
 
Example 2:
Input:
V = 3, E = 3
adj = {{{1, 1}, {2, 6}}, {{2, 3}, {0, 1}}, {{1, 3}, {0, 6}}}
S = 2
Output:
4 3 0
Explanation:
For nodes 2 to 0, we can follow the path-
2-1-0. This has a distance of 1+3 = 4,
whereas the path 2-0 has a distance of 6. So,
the Shortest path from 2 to 0 is 4.
The shortest distance from 0 to 1 is 1 .
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function dijkstra()  which takes the number of vertices V and an adjacency list adj as input parameters and Source vertex S returns a list of integers, where ith integer denotes the shortest distance of the ith node from the Source node.  Here adj[i] contains a list of lists containing two integers where the first integer j denotes that there is an edge between i and j and the second integer w denotes that the weight between edge i and j is w.
 
Expected Time Complexity: O(V^{2}).
Expected Auxiliary Space: O(V^{2}).
 
Constraints:
1  ≤  V  ≤  1000
0  ≤  adj[i][j]  ≤  1000
1 ≤ adj.size() ≤ [ (V*(V - 1)) / 2 ]
0  ≤  S < V

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: class Solution:



    #Function to find the shortest distance of all the vertices

    #from the source vertex S.

    def dijkstra(self, V, adj, S):

        #code here

Solutions:
import heapq, sys

class Solution:

	def util(self, graph, vis, pq, dis, s, V):
		while len(pq) > 0:
			while len(pq) > 0 and vis[pq[0][1]] == 1:
				heapq.heappop(pq)
			if len(pq) > 0:
				temp = heapq.heappop(pq)
				vis[temp[1]] = 1
				for i in graph[temp[1]]:
					i[1] = min(dis[i[0]], temp[0] + i[1])
					dis[i[0]] = i[1]
					heapq.heappush(pq, (dis[i[0]], i[0]))
		return dis

	def dijkstra(self, V, adj, S):
		vis = [0 for i in range(V)]
		dis = [sys.maxsize for _ in range(V)]
		pq = [(0, S)]
		dis[S] = 0
		heapq.heapify(pq)
		return self.util(adj, vis, pq, dis, S, V)


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		pq = []
		heapq.heappush(pq, (0, S))
		dist = [float('inf')] * V
		dist[S] = 0
		while pq:
			(d, u) = heapq.heappop(pq)
			for (v, w) in adj[u]:
				if dist[v] > dist[u] + w:
					dist[v] = dist[u] + w
					heapq.heappush(pq, (dist[v], v))
		return dist


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf')] * V
		dist[S] = 0
		q = []
		heapq.heapify(q)
		heapq.heappush(q, (0, S))
		while q:
			(distance, node) = heapq.heappop(q)
			for i in adj[node]:
				adjNode = i[0]
				edgeWeight = i[1]
				if distance + edgeWeight < dist[adjNode]:
					dist[adjNode] = distance + edgeWeight
					heapq.heappush(q, (dist[adjNode], adjNode))
		return dist


from heapq import heapify, heappush, heappop

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('+inf') for _ in range(V)]
		dist[S] = 0
		vis = [False] * V
		q = []
		heapify(q)
		heappush(q, (0, S))
		while len(q) != 0:
			(x, y) = heappop(q)
			vis[y] = True
			for (i, j) in adj[y]:
				if not vis[i] and j + dist[y] < dist[i]:
					dist[i] = j + dist[y]
					heappush(q, (dist[i], i))
		return dist


class Solution:

	def dijkstra(self, V, adj, S):
		return my_dijkstra(adj, S)
from queue import PriorityQueue

def my_dijkstra(G, s):
	n = len(G)
	distance = [-1] * n
	visited = [False] * n
	parent = [None] * n
	distance[s] = 0
	pq = PriorityQueue()
	pq.put((0, s))
	while not pq.empty():
		(_, u) = pq.get()
		if not visited[u]:
			for (v, w) in G[u]:
				if distance[v] == -1 or distance[v] > distance[u] + w:
					distance[v] = distance[u] + w
					parent[v] = u
					pq.put((distance[v], v))
	return distance


from collections import defaultdict
import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		pq = []
		dist = [1000000000.0] * V
		dist[S] = 0
		heapq.heappush(pq, (0, S))
		while pq:
			(dis, node) = heapq.heappop(pq)
			for (adjnode, edW) in adj[node]:
				if dist[adjnode] > dis + edW:
					dist[adjnode] = dis + edW
					heapq.heappush(pq, (dis + edW, adjnode))
		return dist


import math
import heapq
from collections import deque

class Solution:

	def dijkstra(self, V, adj, S):
		dis = [math.inf for i in range(V)]
		dis[S] = 0
		q = []
		q.append([0, S])
		heapq.heapify(q)
		while q:
			(cost, node) = heapq.heappop(q)
			for i in adj[node]:
				if cost + i[1] < dis[i[0]]:
					dis[i[0]] = cost + i[1]
					heapq.heappush(q, [cost + i[1], i[0]])
		return dis
		pass


from heapq import *

class Solution:

	def dijkstra(self, v, adj, src):
		dist = [float('inf') for i in range(v)]
		min_heap = []
		dist[src] = 0
		heappush(min_heap, [0, src])
		while min_heap:
			node = heappop(min_heap)
			dis = node[0]
			vert = node[1]
			for it in adj[vert]:
				if dis + it[1] < dist[it[0]]:
					dist[it[0]] = dis + it[1]
					heappush(min_heap, [dis + it[1], it[0]])
		return dist


from heapq import heappush, heappop

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf')] * V
		dist[S] = 0
		li = [(0, S)]
		s = set()
		while len(li):
			(d, node) = heappop(li)
			if node in s:
				continue
			s.add(node)
			for (j, cost) in adj[node]:
				if j in s:
					continue
				if dist[j] > dist[node] + cost:
					dist[j] = dist[node] + cost
					heappush(li, (dist[j], j))
		return dist


from heapq import heapify, heappush, heappop

class Solution:

	def dijkstra(self, V, adj, S):
		heap = []
		heapify(heap)
		dist = [float('inf') for _ in range(V)]
		dist[S] = 0
		heappush(heap, (0, S))
		while heap:
			(dis, node) = heappop(heap)
			for ele in adj[node]:
				edgeWeight = ele[1]
				adjNode = ele[0]
				if dis + edgeWeight < dist[adjNode]:
					dist[adjNode] = dis + edgeWeight
					heappush(heap, (dist[adjNode], adjNode))
		return dist


from collections import defaultdict
import heapq
INF = float('inf')

class Solution:

	def dijkstra(self, V, adj, S):
		d = defaultdict(list)
		for i in range(V):
			for j in range(len(adj[i])):
				(s, n) = (i, adj[i][j][0])
				weight = adj[i][j][1]
				d[s].append([n, weight])
		dist = [INF for _ in range(V)]
		dist[S] = 0
		q = [[0, S]]
		while q:
			(t, C) = heapq.heappop(q)
			for (N, T) in d[C]:
				if t + T < dist[N]:
					dist[N] = t + T
					heapq.heappush(q, [t + T, N])
		return dist


class Solution:

	def dijkstra(self, V, adj, S):
		distance = [sys.maxsize for i in range(V)]
		distance[S] = 0
		s = set()
		s.add((0, S))
		while len(s) != 0:
			(d, topnode) = s.pop()
			for neighbour in adj[topnode]:
				if distance[neighbour[0]] > distance[topnode] + neighbour[1]:
					distance[neighbour[0]] = distance[topnode] + neighbour[1]
					s.add((distance[neighbour[0]], neighbour[0]))
		return distance


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		map_dict = {}
		for i in range(V):
			map_dict[i] = [100000000, i]
		map_dict[S] = [0, S]
		heap_list = list(map_dict.values())
		heapq.heapify(heap_list)
		output = [-1 for i in range(V)]
		while len(heap_list) > 0:
			val = heapq.heappop(heap_list)
			output[val[1]] = val[0]
			map_dict.pop(val[1])
			neigh = adj[val[1]]
			for n in neigh:
				vertex = n[0]
				distance = n[1]
				if vertex in map_dict and distance + val[0] < map_dict[vertex][0]:
					map_dict[vertex][0] = distance + val[0]
			heap_list = list(map_dict.values())
			heapq.heapify(heap_list)
		return output


import heapq
from collections import defaultdict

class Solution:

	def dijkstra(self, n, adj, src):
		g = defaultdict(list)
		for u in range(n):
			if len(adj[u]) == 0:
				continue
			for (v, t) in adj[u]:
				g[u].append((t, v))
				g[v].append((t, u))
		minHeap = [(0, src)]
		done = set()
		time = [0] * n
		while minHeap:
			(t1, n1) = heapq.heappop(minHeap)
			if n1 in done:
				continue
			done.add(n1)
			time[n1] = t1
			for (t2, n2) in g[n1]:
				if n2 in done:
					continue
				heapq.heappush(minHeap, (t1 + t2, n2))
		return time


import heapq as hq

class Solution:

	def dijkstra(self, V, adj, S):
		history = set()
		history.add((S, 0))
		distance = [float('inf')] * V
		distance[S] = 0
		while history:
			(node, dist) = history.pop()
			for (adjNode, nextDist) in adj[node]:
				if dist + nextDist < distance[adjNode]:
					if distance[adjNode] != float('inf') and (adjNode, distance[adjNode]) in history:
						history.remove((adjNode, distance[adjNode]))
					distance[adjNode] = dist + nextDist
					history.add((adjNode, distance[adjNode]))
		return distance


import heapq as hq

class Solution:

	def dijkstra(self, V, adj, S):
		history = [[S, 0]]
		distance = [float('inf')] * V
		distance[S] = 0
		hq.heapify(history)
		while history:
			(node, dist) = hq.heappop(history)
			for (adjNode, nextDist) in adj[node]:
				if dist + nextDist < distance[adjNode]:
					distance[adjNode] = dist + nextDist
					hq.heappush(history, [adjNode, distance[adjNode]])
		return distance


class Solution:

	def dijkstra(self, V, adj, S):
		import numpy as np
		graph = []
		for i in range(V):
			graph.append([0] * V)
		for i in range(V):
			for j in adj[i]:
				graph[i][j[0]] = j[1]
		dist = [np.inf] * V
		sptset = [False] * V
		dist[S] = 0
		for i in range(V - 1):
			u = Solution.mindist(dist, sptset)
			sptset[u] = True
			for j in range(V):
				if not sptset[j] and graph[u][j] and (dist[u] != np.inf) and (dist[u] + graph[u][j] < dist[j]):
					dist[j] = dist[u] + graph[u][j]
		return dist

	def mindist(dist, sptset):
		import numpy as np
		min = np.inf
		min_index = 0
		for i in range(len(dist)):
			if dist[i] <= min and sptset[i] == False:
				min = dist[i]
				min_index = i
		return min_index


from collections import defaultdict
from queue import PriorityQueue

class Solution:

	def dijkstra(self, V, adj, S):
		q = PriorityQueue()
		q.put((0, S))
		dist = [float('inf')] * V
		dist[S] = 0
		while not q.empty():
			(wt, node) = q.get()
			for (adjNode, edW) in adj[node]:
				if wt + edW < dist[adjNode]:
					dist[adjNode] = wt + edW
					q.put((dist[adjNode], adjNode))
		return dist


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		distances = [float('inf')] * V
		distances[S] = 0
		pq = [(0, S)]
		while pq:
			(dist, u) = heapq.heappop(pq)
			for (v, weight) in adj[u]:
				new_dist = dist + weight
				if new_dist < distances[v]:
					distances[v] = new_dist
					heapq.heappush(pq, (new_dist, v))
		return distances


class Solution:

	def dijkstra(self, V, adj, S):
		dis = [-1 for i in range(len(adj))]
		vis = [0 for i in range(len(adj))]
		st = set()
		st.add((0, S))
		dis[S] = 0
		while len(st) != 0:
			node = min(st)
			st.remove(node)
			if vis[node[1]] == 1:
				continue
			for i in adj[node[1]]:
				if dis[i[0]] == -1 or dis[i[0]] >= node[0] + i[1]:
					dis[i[0]] = node[0] + i[1]
					st.add((dis[i[0]], i[0]))
				else:
					pass
			vis[node[1]] = 1
		return dis


from heapq import heapify, heappush, heappop
from collections import defaultdict

class Solution:

	def dijkstra(self, V, adjl, S):
		pq = []
		ret = [float('inf')] * V
		adj = defaultdict(list)
		for (i, edges) in enumerate(adjl):
			for (v, w) in edges:
				adj[i].append((w, v))
		ret[S] = 0
		heappush(pq, (0, S))
		while pq:
			(weight, vertex) = heappop(pq)
			for (w, v) in adj[vertex]:
				if ret[v] > w + weight:
					ret[v] = w + weight
					heappush(pq, (ret[v], v))
		for i in range(V):
			if ret[i] == float('inf'):
				ret[i] = -1
		return ret


from heapq import *

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf') for i in range(V)]
		dist[S] = 0
		min_heap = []
		heappush(min_heap, (0, S))
		while min_heap:
			(d, u) = heappop(min_heap)
			for (v, e) in adj[u]:
				relax(u, v, dist, e, min_heap)
		return dist

def relax(u, v, dist, e, min_heap):
	if dist[v] > dist[u] + e:
		dist[v] = dist[u] + e
		heappush(min_heap, (dist[v], v))


from heapq import heappush, heappop

class Solution:

	def dijkstra(self, V, adj, S):
		distance = [float('inf')] * V
		distance[S] = 0
		heap = list()
		heappush(heap, (0, S))
		while heap:
			(nodedist, node) = heappop(heap)
			for (adjnode, adjdist) in adj[node]:
				if distance[adjnode] > nodedist + adjdist:
					heappush(heap, (nodedist + adjdist, adjnode))
					distance[adjnode] = nodedist + adjdist
		return distance


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		distance = [1000000009 for i in range(V)]
		distance[S] = 0
		pq = [[0, S]]
		while len(pq) != 0:
			(currDist, currNode) = heapq.heappop(pq)
			for (neigh, wt) in adj[currNode]:
				dist = currDist + wt
				if dist < distance[neigh]:
					distance[neigh] = dist
					heapq.heappush(pq, [dist, neigh])
		return distance


import collections

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf')] * V
		dist[S] = 0
		q = collections.deque()
		q.append(S)
		while q:
			z = q.popleft()
			for adj_node in adj[z]:
				curr_distance = dist[z]
				new_wt = adj_node[1] + curr_distance
				if dist[adj_node[0]] > new_wt:
					dist[adj_node[0]] = new_wt
					q.append(adj_node[0])
		return dist


import heapq

class Solution:

	def dijkstra(self, v, adj, s):
		distances = [float('Inf')] * v
		distances[s] = 0
		queue = []
		heapq.heappush(queue, (0, s))
		processed = set()
		while queue and len(processed) < v - 1:
			(dist, vertex) = heapq.heappop(queue)
			processed.add(vertex)
			for (child, distance) in adj[vertex]:
				if child in processed:
					continue
				if distances[child] > distance + dist:
					distances[child] = distance + dist
					heapq.heappush(queue, (distances[child], child))
		return distances


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		heap = [(0, S)]
		heapq.heapify(heap)
		distances = [float('inf') for i in range(V)]
		distances[S] = 0
		while heap:
			(distance, element) = heapq.heappop(heap)
			for (neigh, dist) in adj[element]:
				if distance + dist < distances[neigh]:
					distances[neigh] = distance + dist
					heapq.heappush(heap, (distance + dist, neigh))
		return distances


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		visited_vertex = set()
		heap = [(0, S)]
		heapq.heapify(heap)
		distances = [0 for i in range(V)]
		while heap:
			(distance, element) = heapq.heappop(heap)
			if element in visited_vertex:
				continue
			distances[element] = distance
			visited_vertex.add(element)
			for (neigh, dist) in adj[element]:
				if neigh not in visited_vertex:
					x = distance + dist
					heapq.heappush(heap, (x, neigh))
		return distances


from queue import PriorityQueue
import math

class Solution:

	def dijkstra(self, V, adj, S):
		d = {}
		for (ind, i) in enumerate(adj):
			d[ind] = {k[0]: k[1] for k in i}
		min_dist = {x: math.inf for x in d}
		min_dist[S] = 0
		pq = PriorityQueue()
		pq.put((S, 0))
		while not pq.empty():
			(present_node, dist) = pq.get()
			for i in d[present_node]:
				if dist + d[present_node][i] < min_dist[i]:
					pq.put((i, dist + d[present_node][i]))
					min_dist[i] = dist + d[present_node][i]
		return min_dist.values()


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf')] * len(adj)
		dist[S] = 0
		queue = []
		heapq.heappush(queue, (0, S))
		while queue:
			(curr_dist, node) = heapq.heappop(queue)
			for (nei, wt) in adj[node]:
				if curr_dist + wt < dist[nei]:
					dist[nei] = curr_dist + wt
					heapq.heappush(queue, (dist[nei], nei))
		return dist


class Solution:

	def dijkstra(self, V, adj, S):
		solved = set()
		dist = [float('inf') for i in range(V)]
		dist[S] = 0
		while len(solved) != V:
			u = find(dist, solved)
			solved.add(u)
			for j in range(len(adj[u])):
				(v, e) = adj[u][j]
				relax(u, v, dist, e)
		return dist

def find(dist, solved):
	min_value = float('inf')
	index = -1
	for i in range(len(dist)):
		if dist[i] < min_value and i not in solved:
			min_value = dist[i]
			index = i
	return index

def relax(u, v, dist, e):
	if dist[v] > dist[u] + e:
		dist[v] = dist[u] + e


class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf') for i in range(V)]
		dist[S] = 0
		processed_set = [False for i in range(V)]
		for i in range(V):
			u = get_value(dist, processed_set)
			processed_set[u] = True
			for j in range(len(adj[u])):
				(v, e) = adj[u][j]
				relax(dist, u, v, e)
		return dist

def get_value(dist, processed_set):
	val = float('inf')
	index = -1
	for i in range(len(dist)):
		if dist[i] < val and processed_set[i] == False:
			val = dist[i]
			index = i
	return index

def relax(dist, u, v, edge):
	if dist[v] > dist[u] + edge:
		dist[v] = dist[u] + edge


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		timer = [float('inf') for i in range(V)]
		timer[S] = 0
		vis = [False for i in range(V)]
		li = []
		heap = heapq.heappush(li, [0, S])
		while len(li) > 0:
			(time, node) = heapq.heappop(li)
			if vis[node] == False:
				vis[node] = True
				timer[node] = min(timer[node], time)
				for (edge, wei) in adj[node]:
					if vis[edge] == False:
						heapq.heappush(li, [time + wei, edge])
		return timer


import heapq
from sys import maxsize

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [maxsize] * V
		dist[S] = 0
		min_heap = []
		heapq.heappush(min_heap, (0, S))
		while min_heap:
			(d, node) = heapq.heappop(min_heap)
			for (nbr, wt) in adj[node]:
				if d + wt < dist[nbr]:
					dist[nbr] = d + wt
					heapq.heappush(min_heap, (dist[nbr], nbr))
		return dist


from queue import PriorityQueue

class Solution:

	def dijkstra(self, V, adj, S):
		res = [-1] * V
		res[S] = 0
		q = PriorityQueue()
		q.put((0, S))
		while not q.empty():
			(_, u) = q.get()
			for (v, w) in adj[u]:
				if res[v] == -1 or res[v] > res[u] + w:
					res[v] = res[u] + w
					q.put((res[v], v))
		return res


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('infinity')] * V
		dist[S] = 0
		min_heap = [(0, S)]
		heapq.heapify(min_heap)
		while len(min_heap):
			popp = heapq.heappop(min_heap)
			(distance, node) = popp
			for neighbour in adj[node]:
				if distance + neighbour[1] < dist[neighbour[0]]:
					dist[neighbour[0]] = distance + neighbour[1]
					heapq.heappush(min_heap, (dist[neighbour[0]], neighbour[0]))
		return dist


from collections import *

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf') for i in range(V)]
		dist[S] = 0
		q = deque([])
		q.append(S)
		while q:
			a = q.popleft()
			for i in adj[a]:
				(v, wt) = (i[0], i[1])
				if dist[v] > dist[a] + wt:
					dist[v] = dist[a] + wt
					q.append(v)
		return dist


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf')] * V
		dist[S] = 0
		h = []
		heapq.heapify(h)
		heapq.heappush(h, (0, S))
		while h:
			(distance, node) = heapq.heappop(h)
			for (no, weight) in adj[node]:
				if dist[no] > dist[node] + weight:
					dist[no] = dist[node] + weight
					heapq.heappush(h, (dist[no], no))
		return dist


from heapq import heapify, heappush, heappop
import math

class Solution:

	def dijkstra(self, V, adj, S):
		heap = [(S, 0)]
		dist = [math.inf] * V
		dist[S] = 0
		while heap:
			(n, d) = heappop(heap)
			for (neigh, weight) in adj[n]:
				new_weight = d + weight
				if new_weight < dist[neigh]:
					dist[neigh] = new_weight
					heappush(heap, (neigh, new_weight))
		return dist


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		distance = {}
		heap = [(0, S)]
		while heap:
			(time, node) = heapq.heappop(heap)
			if node in distance:
				continue
			distance[node] = time
			for (target, cost) in adj[node]:
				if not target in distance:
					heapq.heappush(heap, (time + cost, target))
		return [distance[i] for i in range(V)]


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf') for _ in range(V)]
		dist[S] = 0
		queue = [[0, S]]
		while len(queue) > 0:
			temp = heapq.heappop(queue)
			node = temp[1]
			distance = temp[0]
			for x in adj[node]:
				wt = x[1]
				n = x[0]
				if distance + wt < dist[n]:
					dist[n] = distance + wt
					heapq.heappush(queue, [distance + wt, n])
		return dist


import heapq
from collections import deque

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf') for i in range(V)]
		dist[S] = 0
		q = deque([])
		q.append(S)
		while q:
			a = q.popleft()
			for i in adj[a]:
				(f, g) = (i[0], i[1])
				if dist[f] > dist[a] + g:
					dist[f] = dist[a] + g
					q.append(f)
		return dist


from queue import PriorityQueue

class Solution:

	def dijkstra(self, V, adj, S):
		q = PriorityQueue()
		dist = [float('inf')] * V
		dist[S] = 0
		q.put((0, S))
		while not q.empty():
			item = q.get()
			dis = item[0]
			node = item[1]
			for i in adj[node]:
				nxt = i[0]
				nextdist = i[1]
				if dist[nxt] > dis + nextdist:
					dist[nxt] = dis + nextdist
					q.put((dist[nxt], nxt))
		return dist


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [1000000000.0] * V
		dist[S] = 0
		pq = [(0, S)]
		heapq.heapify(pq)
		while len(pq) != 0:
			elem = heapq.heappop(pq)
			dis = elem[0]
			node = elem[1]
			for it in adj[node]:
				edgeWeight = it[1]
				adjNode = it[0]
				if dis + edgeWeight < dist[adjNode]:
					dist[adjNode] = dis + edgeWeight
					heapq.heappush(pq, (dist[adjNode], adjNode))
		return dist


import heapq
from collections import deque

class Solution:

	def dijkstra(self, V, adj, S):
		res = [sys.maxsize] * V
		res[S] = 0
		que = deque([(0, S)])
		while que:
			(dis, node) = que.popleft()
			for (adjNode, adjDis) in adj[node]:
				if dis + adjDis < res[adjNode]:
					res[adjNode] = dis + adjDis
					que.append((dis + adjDis, adjNode))
		return res


from queue import PriorityQueue

class Solution:

	def dijkstra(self, v, mat, s):
		q = PriorityQueue()
		dis = [10000000] * v
		dis[s] = 0
		q.put([0, s])
		while not q.empty():
			node = q.get()
			for i in mat[node[1]]:
				if dis[i[0]] > node[0] + i[1]:
					dis[i[0]] = node[0] + i[1]
					q.put([dis[i[0]], i[0]])
		return dis


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		res = [sys.maxsize] * V
		res[S] = 0
		heap = [(0, S)]
		while heap:
			(dis, node) = heapq.heappop(heap)
			for (adjNode, adjDis) in adj[node]:
				if dis + adjDis < res[adjNode]:
					res[adjNode] = dis + adjDis
					heapq.heappush(heap, (dis + adjDis, adjNode))
		return res


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		n = V
		(res, visited) = ([sys.maxsize] * V, [False] * V)
		heap = [(0, S)]
		while heap:
			(dis, node) = heapq.heappop(heap)
			if dis < res[node]:
				res[node] = dis
			visited[node] = True
			for (adjNode, adjDis) in adj[node]:
				if not visited[adjNode]:
					heapq.heappush(heap, (dis + adjDis, adjNode))
		return res


from collections import defaultdict
from queue import PriorityQueue

class Solution:

	def dijkstra(self, V, adj, S):
		q = PriorityQueue()
		dist = [float('inf')] * V
		dist[S] = 0
		q.put((0, S))
		while not q.empty():
			(dis, node) = q.get()
			for i in adj[node]:
				edgWeight = i[1]
				adjNode = i[0]
				if dis + edgWeight < dist[adjNode]:
					dist[adjNode] = dis + edgWeight
					q.put((dist[adjNode], adjNode))
		return dist


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		heap = set()
		heap.add((0, S))
		distance = [999999] * V
		distance[S] = 0
		while heap:
			node = heap.pop()
			for i in adj[node[1]]:
				if node[0] + i[1] < distance[i[0]]:
					heap.add((node[0] + i[1], i[0]))
					if distance[i[0]] != 999999:
						heap.discard((distance[i[0]], i[1]))
					distance[i[0]] = node[0] + i[1]
		return distance


class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf')] * V
		dist[S] = 0
		s = set()
		s.add((0, S))
		while len(s) != 0:
			top = list(s)[0]
			nod_dist = top[0]
			node = top[1]
			s.remove(list(s)[0])
			for neighbour in adj[node]:
				if nod_dist + neighbour[1] < dist[neighbour[0]]:
					rec = (dist[neighbour[0]], neighbour[0])
					if rec[1] in s:
						s.remove(rec)
					dist[neighbour[0]] = nod_dist + neighbour[1]
					s.add((dist[neighbour[0]], neighbour[0]))
		return dist


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dis = [float('inf') for i in range(V)]
		dis[S] = 0
		res = []
		heap = [[0, S]]
		vis = set()
		vis.add(S)
		while len(heap) != 0:
			(wt, node) = heapq.heappop(heap)
			vis.add(node)
			for v in adj[node]:
				nbr = v[0]
				w = v[1]
				if nbr not in vis and dis[nbr] > dis[node] + w:
					dis[nbr] = dis[node] + w
					heapq.heappush(heap, [dis[nbr], nbr])
		for i in dis:
			if i > 1000000000.0:
				res.append(-1)
			else:
				res.append(i)
		return res


class Solution:

	def dijkstra(self, V, adj, S):
		finalized_vertexes = [False for _ in range(V)]
		minimum_distances = [float('inf') for _ in range(V)]
		minimum_distances[S] = 0
		for _ in range(V - 1):
			minimum_vertex = None
			for vertex in range(V):
				if not finalized_vertexes[vertex] and (minimum_vertex is None or minimum_distances[vertex] < minimum_distances[minimum_vertex]):
					minimum_vertex = vertex
			finalized_vertexes[minimum_vertex] = True
			for (adjacent, weight) in adj[minimum_vertex]:
				if not finalized_vertexes[adjacent]:
					minimum_distances[adjacent] = min(minimum_distances[adjacent], minimum_distances[minimum_vertex] + weight)
		return minimum_distances


import sys
from heapq import *

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [sys.maxsize for i in range(V)]
		minheap = []
		heappush(minheap, (0, S))
		dist[S] = 0
		while minheap:
			(dis, node) = heappop(minheap)
			for edge in adj[node]:
				nextNode = edge[0]
				nextDist = edge[1]
				if dist[node] + nextDist < dist[nextNode]:
					dist[nextNode] = dist[node] + nextDist
					heappush(minheap, (dist[nextNode], nextNode))
		return dist


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf') for i in range(V)]
		dist[S] = 0
		pq = []
		heapq.heappush(pq, (0, S))
		while pq:
			(d, node) = heapq.heappop(pq)
			for (nei, wt) in adj[node]:
				if dist[node] + wt < dist[nei]:
					dist[nei] = dist[node] + wt
					heapq.heappush(pq, (dist[nei], nei))
		return dist


import heapq
import math

class Solution:

	def dijkstra(self, V, adj, S):
		heap = [(0, S)]
		optimized_weight = [math.inf] * V
		optimized_weight[S] = 0
		while heap:
			(weight, src) = heapq.heappop(heap)
			for (neigh, neigh_weight) in adj[src]:
				new_weight = weight + neigh_weight
				if new_weight < optimized_weight[neigh]:
					optimized_weight[neigh] = new_weight
					heapq.heappush(heap, (new_weight, neigh))
		return optimized_weight


from heapq import heappop, heappush

class Solution:

	def dijkstra(self, V, adjList, src):
		heap = [(0, src)]
		dis = [float('inf') for _ in range(V)]
		dis[src] = 0
		while heap:
			(curr_dis, node) = heappop(heap)
			for nei in adjList[node]:
				adjNode = nei[0]
				edgeWeight = nei[1]
				if curr_dis + edgeWeight < dis[adjNode]:
					dis[adjNode] = curr_dis + edgeWeight
					heappush(heap, (dis[adjNode], adjNode))
		return dis


from queue import PriorityQueue as PQ

class Solution:

	def dijkstra(self, V, adj, S):
		q = PQ()
		dist = [10 ** 9 for i in range(V)]
		dist[S] = 0
		q.put((0, S))
		while not q.empty():
			x = q.get()
			dis = x[0]
			node = x[1]
			for it in adj[node]:
				edgeWeight = it[1]
				adjNode = it[0]
				if dis + edgeWeight < dist[adjNode]:
					dist[adjNode] = dis + edgeWeight
					q.put((dist[adjNode], adjNode))
		return dist


from queue import PriorityQueue

class Solution:

	def dijkstra(self, V, adj, S):
		pqueue = PriorityQueue()
		parent = [i for i in range(V)]
		minDis = [float('inf') for _ in range(V)]
		minDis[S] = 0
		pqueue.put((0, S))
		while not pqueue.empty():
			(dis, node) = pqueue.get()
			for (neighbor, weight) in adj[node]:
				if weight + dis < minDis[neighbor]:
					minDis[neighbor] = weight + dis
					pqueue.put((minDis[neighbor], neighbor))
					parent[neighbor] = node
		return minDis


from queue import PriorityQueue

class Pair:

	def __init__(self, v, wt):
		self.v = v
		self.wt = wt

	def __lt__(self, other):
		return self.wt < other.wt

class Solution:

	def dijkstra(self, v, adj, S):
		vis = [False] * v
		q = PriorityQueue()
		q.put((0, S))
		ans = [float('inf')] * v
		ans[S] = 0
		while not q.empty():
			(wt, u) = q.get()
			if vis[u]:
				continue
			vis[u] = True
			neighbours = adj[u]
			for (vertex, edge_weight) in neighbours:
				if ans[vertex] > ans[u] + edge_weight:
					ans[vertex] = ans[u] + edge_weight
					q.put((ans[vertex], vertex))
		return ans


from heapq import heapify, heappush, heappop

class Solution:

	def dijkstra(self, V, adj, S):
		cost = [0] * V
		queue = [[0, S]]
		heapify(queue)
		vis = []
		while queue:
			(dist, node) = heappop(queue)
			if node in vis:
				continue
			cost[node] = dist
			vis.append(node)
			for i in adj[node]:
				if i[0] not in vis:
					heappush(queue, [i[1] + dist, i[0]])
		return cost


class Solution:

	def dijkstra(self, v, adj, s):
		st = set()
		st.add((s, 0))
		stk = [(s, 0)]
		dist = [10000000000.0] * v
		dist[s] = 0
		while stk:
			node = stk.pop()
			parent = node[0]
			parentDist = node[1]
			for nbr in adj[parent]:
				child = nbr[0]
				cost = nbr[1]
				if parentDist + cost < dist[child]:
					temp = (child, dist[child])
					if temp in st:
						st.remove(temp)
					dist[child] = parentDist + cost
					st.add((child, dist[child]))
					stk.append((child, dist[child]))
		return dist


import heapq
import sys

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [sys.maxsize] * V
		pq = []
		dist[S] = 0
		heapq.heappush(pq, (S, 0))
		while pq:
			node = heapq.heappop(pq)
			for i in adj[node[0]]:
				if dist[node[0]] + i[1] < dist[i[0]]:
					dist[i[0]] = dist[node[0]] + i[1]
					heapq.heappush(pq, (i[0], i[1]))
		return dist


from queue import PriorityQueue

class Solution:

	def dijkstra(self, V, adj, S):
		D = {v: float('inf') for v in range(V)}
		D[S] = 0
		pq = PriorityQueue()
		pq.put((0, S))
		while not pq.empty():
			(dist, currentNode) = pq.get()
			for obj in adj[currentNode]:
				(v, distance) = obj
				old_cost = D[v]
				new_cost = distance + D[currentNode]
				if new_cost < old_cost:
					pq.put((new_cost, v))
					D[v] = new_cost
		return D.values()


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		q = [(S, 0)]
		res = [sys.maxsize] * V
		res[S] = 0
		while q:
			(i, curw) = q.pop(0)
			for (j, prevw) in adj[i]:
				if curw + prevw < res[j]:
					res[j] = curw + prevw
					heapq.heappush(q, (j, curw + prevw))
		return res


import math
from typing import Iterable, List, Optional, Tuple, Union
import sys

class Solution:

	def _get_adj_matrix_from_adj_list(graph: List[List[Iterable[Union[int, float]]]], V: int=None) -> List[List[Union[int, float]]]:
		if V is None:
			V = len(graph)
		adj_mat = [[math.inf] * V for _ in range(V)]
		for (u, edges) in enumerate(graph):
			for (v, weight) in edges:
				adj_mat[u][v] = weight
		return adj_mat

	def dijkstra(self, V, adj, S):
		graph = Solution._get_adj_matrix_from_adj_list(adj, V)
		weight = [math.inf] * V
		weight[S] = 0
		prev = [None] * V
		processed = [False] * V
		for i in range(V):
			min_dist = math.inf
			min_vertex = None
			for u in range(V):
				if not processed[u] and weight[u] < min_dist:
					min_dist = weight[u]
					min_vertex = u
			processed[min_vertex] = True
			for v in range(V):
				if not processed[v] and math.isfinite(graph[min_vertex][v]):
					u_v_weight = weight[min_vertex] + graph[min_vertex][v]
					if u_v_weight < weight[v]:
						weight[v] = u_v_weight
						prev[v] = min_vertex
		result = [0] * V
		for i in range(V):
			j = i
			t = 0
			while j != S:
				t += graph[prev[j]][j]
				j = prev[j]
			result[i] = t
		return result


import heapq
import sys

class Solution:

	def dijkstra(self, V, adj, S):
		pq = []
		distTo = [float('inf')] * V
		distTo[S] = 0
		heapq.heappush(pq, (0, S))
		while pq:
			(dis, node) = heapq.heappop(pq)
			for (v, w) in adj[node]:
				if dis + w < distTo[v]:
					distTo[v] = dis + w
					heapq.heappush(pq, (dis + w, v))
		return distTo


import heapq
import math

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [math.inf] * V
		dist[S] = 0
		q = [[0, S]]
		heapq.heapify(q)
		while q:
			(d, node) = heapq.heappop(q)
			for v in adj[node]:
				edgeweight = v[1]
				adjnode = v[0]
				if d + edgeweight < dist[adjnode]:
					dist[adjnode] = d + edgeweight
					heapq.heappush(q, [dist[adjnode], adjnode])
		return dist


from heapq import heappush, heappop, heapify

class Solution:

	def dijkstra(self, V, adj, S):
		dis_arr = [float('inf')] * V
		dis_arr[S] = 0
		heap = [(0, S)]
		heapify(heap)
		while len(heap) > 0:
			(dis, node) = heappop(heap)
			for (edge_node, edge_dis) in adj[node]:
				if dis + edge_dis < dis_arr[edge_node]:
					dis_arr[edge_node] = dis + edge_dis
					heappush(heap, (dis_arr[edge_node], edge_node))
		return dis_arr


from heapq import *

class Solution:

	def dijkstra(self, V, adj, S):
		dis = [float('inf')] * V
		dis[S] = 0
		queue = []
		heappush(queue, (0, S))
		visited = [0] * V
		while queue:
			(d, j) = heappop(queue)
			if visited[j] == 0:
				visited[j] = 1
			for (i, d1) in adj[j]:
				if dis[i] > dis[j] + d1:
					dis[i] = dis[j] + d1
					heappush(queue, (dis[j] + d1, i))
		for i in range(V):
			if visited[i] == 0:
				dis[i] = -1
		return dis


import math

class Solution:

	def dijkstra(self, V, adj, S):
		visited = [False] * V
		d = [math.inf] * V
		visited[S] = True
		for neighbour in adj[S]:
			n = neighbour[0]
			w = neighbour[1]
			d[n] = w
		for i in range(V):
			curr_v = self.min_v(d, visited)
			if curr_v is None:
				break
			visited[curr_v] = True
			for neighbour in adj[curr_v]:
				if d[curr_v] + neighbour[1] < d[neighbour[0]] and visited[neighbour[0]] == False:
					d[neighbour[0]] = d[curr_v] + neighbour[1]
		d[S] = 0
		return d

	def min_v(self, arr, visited):
		min = math.inf
		min_index = None
		for i in range(len(arr)):
			if arr[i] < min and visited[i] == False:
				min = arr[i]
				min_index = i
		return min_index


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dis = [float('inf') for _ in range(V)]
		pq = [(0, S)]
		dis[S] = 0
		while pq:
			(d, u) = heapq.heappop(pq)
			for (v, e) in adj[u]:
				if d + e < dis[v]:
					dis[v] = d + e
					heapq.heappush(pq, (dis[v], v))
		return dis


class Solution:

	def dijkstra(self, V, adj, S):
		INF = float('inf')
		DP = [INF for i in range(V)]
		DP[S] = 0
		visit = [False for _ in range(V)]

		def getmin():
			mins = INF
			minindx = 0
			for i in range(V):
				if visit[i] == False and DP[i] < mins:
					mins = DP[i]
					minindx = i
			return minindx
		for i in range(V):
			minvit = getmin()
			visit[minvit] = True
			for (d, w) in adj[minvit]:
				if visit[d] == False:
					DP[d] = min(DP[d], DP[minvit] + w)
		return DP


import heapq

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf')] * V
		heap = []
		heapq.heappush(heap, (0, S))
		dist[S] = 0
		while heap:
			(di, node) = heapq.heappop(heap)
			for (neigh, d) in adj[node]:
				if dist[node] + d < dist[neigh]:
					dist[neigh] = dist[node] + d
					heapq.heappush(heap, (dist[neigh], neigh))
		return dist


from queue import PriorityQueue

def shortest_distance(v, adj: [[[]]], source_vertex: int):
	data_queue = PriorityQueue()
	visited_dist_map = {}
	for i in range(v):
		visited_dist_map[i] = [False, float('inf')]
	visited_dist_map[source_vertex][1] = 0
	data_queue.put((0, source_vertex))
	while len(data_queue.queue) > 0:
		vertex_weight_data = data_queue.get()
		dist = vertex_weight_data[0]
		vertex = vertex_weight_data[1]
		if visited_dist_map[vertex][0]:
			continue
		visited_dist_map[vertex][0] = True
		for neighbor_weight in adj[vertex]:
			neighbor = neighbor_weight[0]
			weight = neighbor_weight[1]
			curr_dist = visited_dist_map[neighbor][1]
			if curr_dist > weight + dist:
				visited_dist_map[neighbor][1] = weight + dist
				data_queue.put((weight + dist, neighbor))
	final_arr = []
	for value in visited_dist_map.values():
		final_arr.append(value[1])
	return final_arr

class Solution:

	def dijkstra(self, V, adj, S):
		return shortest_distance(V, adj, S)


import heapq
from heapq import heapify, heappush, heappop

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [float('inf')] * V
		dist[S] = 0
		minHeap = [(0, S)]
		while minHeap:
			(dis, node) = heapq.heappop(minHeap)
			for i in adj[node]:
				newedge = i[1]
				newnode = i[0]
				if dis + newedge < dist[newnode]:
					dist[newnode] = dis + newedge
					heapq.heappush(minHeap, (dist[newnode], newnode))
		return dist


class Solution:

	def dijkstra(self, V, adj, S):
		max_w = 1000 * V * (V - 1) / 2
		max_weights = [max_w] * V
		max_weights[S] = 0
		not_visited = [S]
		while not_visited:
			v = not_visited.pop()
			for (next_v, w) in adj[v]:
				if max_weights[v] + w < max_weights[next_v]:
					max_weights[next_v] = max_weights[v] + w
					not_visited.append(next_v)
		return max_weights


import heapq
import math

class Solution:

	def dijkstra(self, V, adj, S):
		distances = [math.inf for i in range(V)]
		distances[S] = 0
		pq = [(0, S)]
		while pq:
			(uw, u) = heapq.heappop(pq)
			if uw > distances[u]:
				continue
			for (v, vw) in adj[u]:
				path_distance = vw + distances[u]
				if distances[v] > path_distance:
					distances[v] = path_distance
					heapq.heappush(pq, (path_distance, v))
		return distances


class Solution:

	def dijkstra(self, V, adj, S):
		INF = 46810212
		dist = [INF] * V
		dist[S] = 0
		fin = [False for i in range(V)]
		for count in range(V - 1):
			u = -1
			for i in range(V):
				if fin[i] == False and (u == -1 or dist[i] < dist[u]):
					u = i
			fin[u] = True
			for v in range(V):
				if fin[v] == False:
					new_d = INF
					for j in adj[u]:
						if j[0] == v:
							new_d = j[1]
							break
					dist[v] = min(dist[v], new_d + dist[u])
		return dist


import heapq
from collections import defaultdict

class Solution:

	def dijkstra(self, V, adj, S):
		graph = defaultdict(list)
		edges = len(adj)
		for v in range(V):
			if edges > 0:
				for (n, w) in adj[v]:
					graph[v].append((n, w))
			edges -= 1
		queue = [(S, 0)]
		heapq.heapify(queue)
		dist_arr = [float('inf')] * V
		dist_arr[S] = 0
		while queue:
			(node, dist) = heapq.heappop(queue)
			for (n, w) in graph[node]:
				cur_dist = dist + w
				if dist_arr[n] > cur_dist:
					dist_arr[n] = cur_dist
					heapq.heappush(queue, (n, cur_dist))
		dist_arr = [-1 if i == float('inf') else i for i in dist_arr]
		return dist_arr


from sortedcontainers import SortedSet

class Pair:

	def __init__(self, dist, node):
		self.dist = dist
		self.node = node

	def __lt__(self, other):
		return self.dist < other.dist

	def __eq__(self, other):
		return self.dist == other.dist

	def __hash__(self):
		return hash((self.dist, self.node))

class Solution:

	def dijkstra(self, V, adj, S):
		import sys
		dist = [sys.maxsize] * V
		s = SortedSet()
		dist[S] = 0
		s.add(Pair(0, S))
		while len(s):
			curr_node = s.pop(0)
			curr_dist = curr_node.dist
			for nbr in adj[curr_node.node]:
				if dist[nbr[0]] > curr_dist + nbr[1]:
					dist[nbr[0]] = curr_dist + nbr[1]
					s.add(Pair(dist[nbr[0]], nbr[0]))
		return dist


import heapq
import math

class Solution:

	def dijkstra(self, V, adj, S):
		dist = [math.inf] * V
		dist[S] = 0
		pq = []
		heapq.heappush(pq, (0, S))
		while pq:
			(dis, node) = heapq.heappop(pq)
			for (adjNode, adjDist) in adj[node]:
				if dis + adjDist < dist[adjNode]:
					dist[adjNode] = dis + adjDist
					heapq.heappush(pq, (dist[adjNode], adjNode))
		return dist