Due to the second wave of Gorona virus, Geekland imposed another lockdown and Geek has gained some wieght. Now Geek has decided to exercise.
There are N intersections in the city numbered from 0 to N-1 and M bidirectional roads each road connecting two intersections. All the intersections are connected to each-other through some set of roads, i^{th} road connect intersections A[i][0] and A[i][1] and is of length A[i][2].
Every morning Geek will start at intersection src and will run/walk upto intersection dest. Geek only has one hour in the morning so he will choose to cover the shortest path from src to dest.
After planning his exercising schedule, Geek wants to buy the perfect shoes to walk/run in the morning. He goes to Neeman's Shoe factory which is the National Shoe factory of Geekland. 
Geek sees that there are two types of shoes "Neeman's Wool Joggers" and "Neeman's Cotton Classics", "Neeman's Wool Joggers" are good for running and "Neeman's Cotton Classics" are good for walking.
Geek is confused which shoes to buy, so he comes up with a strategy. If the distance he has to cover in the morning is less than or equal to X, then he will walk the distance, therefore he will buy "Neeman's Cotton Classics". If the distance is greater than X, he will buy "Neeman's Wool Joggers". Geek is too lazy to calculate the shortest distance between two intersections src and dest. Help him decide which shoes to buy.
 
Example 1: 
Input:
N = 3, M = 2, src = 0, dest = 2, X = 5
A[][] = {{0, 1, 3},
         {1, 2, 3}}
Output:
Neeman's Wool Joggers
Explanation: 
Shortest path from src to dest is 6 
which is greater than X, hence Geek will
buy "Neeman's Wool Joggers".
 
Example 2: 
Input: 
N = 3, M = 2, src = 0, dest = 2, X = 6 
A[][] = {{0, 1, 3},
         {1, 2, 3}} 
Output: 
Neeman's Cotton Classics 
Explanation: 
Shortest path from src to dest is 6
which is not greater than X, hence Geek 
will Ã¢â¬â¹buy "Neeman's Cotton Classics".
Your Task:
You don't need to read input or print anything. Your task is to complete the function exercise( ) which takes N, M, A[ ][ ], src, dest and X as input parameters and returns string representing the shoes he selects. Either "Neeman's Wool Joggers" or "Neeman's Cotton Classics".
Expected Time Complexity: O((N + M) * Log(M))
Expected Auxiliary Space: O(N + M)
Constraints:
2 ≤ N ≤ 10^{4}
1 ≤ M ≤ min((N*(N-1))/2, 2*10^{5})
0 ≤ A[i][0], A[i][1] < N
0 ≤ src, dest < N
1 ≤ A[i][2], X ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def exercise(self, N, M, A,src, dest,X):
        # code here

Solutions:
from collections import defaultdict
import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		adj = defaultdict(list)
		for (node1, node2, cost) in A:
			adj[node1].append((node2, cost))
			adj[node2].append((node1, cost))
		visited = set()
		heap = [(0, src)]
		while heap:
			(time, node) = heapq.heappop(heap)
			if node in visited:
				continue
			visited.add(node)
			if time > X:
				return "Neeman's Wool Joggers"
			if node == dest:
				return "Neeman's Cotton Classics"
			for (target, cost) in adj[node]:
				if not target in visited:
					heapq.heappush(heap, (time + cost, target))


import heapq as hq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		adj = [[] for i in range(N)]
		for i in A:
			adj[i[0]].append([i[1], i[2]])
			adj[i[1]].append([i[0], i[2]])
		c = [float('inf') for i in range(N)]
		c[src] = 0
		heap = []
		hq.heappush(heap, [0, src])
		while heap:
			top = hq.heappop(heap)
			cu = top[0]
			u = top[1]
			for t in adj[u]:
				v = t[0]
				d = t[1]
				if cu + d < c[v]:
					c[v] = cu + d
					hq.heappush(heap, [c[v], v])
		if c[dest] > X:
			return "Neeman's Wool Joggers"
		return "Neeman's Cotton Classics"


import heapq

def shortestPath(adj, src, dest):
	pq = []
	heapq.heappush(pq, (0, src))
	V = len(adj)
	dist = [float('inf')] * V
	dist[src] = 0
	while pq:
		(d, u) = heapq.heappop(pq)
		for (v, weight) in adj[u]:
			if dist[v] > dist[u] + weight:
				dist[v] = dist[u] + weight
				heapq.heappush(pq, (dist[v], v))
	return dist[dest]

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		adj = [[] for i in range(N)]
		for i in A:
			adj[i[0]].append((i[1], i[2]))
			adj[i[1]].append((i[0], i[2]))
		dist = shortestPath(adj, src, dest)
		if dist > X:
			return "Neeman's Wool Joggers"
		return "Neeman's Cotton Classics"


import heapq
INT_MAX = 1 << 63

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		adj = {u: [] for u in range(N)}
		for i in range(M):
			(u, v, w) = A[i]
			adj[u].append([v, w])
			adj[v].append([u, w])
		dist = [INT_MAX] * N
		dist[src] = 0
		min_heap = []
		heapq.heappush(min_heap, [0, src])
		res_dest = 0
		while min_heap:
			(cost, u) = heapq.heappop(min_heap)
			if u == dest:
				res_dest = cost
				break
			for (v, w) in adj[u]:
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
					heapq.heappush(min_heap, [dist[v], v])
		if res_dest <= X:
			return "Neeman's Cotton Classics"
		return "Neeman's Wool Joggers"


import heapq
from collections import defaultdict

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		heap = [[0, src]]
		dis = [float('inf')] * N
		dis[src] = 0
		adj = defaultdict(list)
		for (i, j, k) in A:
			adj[i].append([k, j])
			adj[j].append([k, i])
		heapq.heapify(heap)
		while heap:
			(dist, node) = heapq.heappop(heap)
			for (ndis, nnode) in adj[node]:
				if ndis + dist < dis[nnode]:
					dis[nnode] = ndis + dist
					heapq.heappush(heap, [dis[nnode], nnode])
		if dis[dest] <= X:
			return "Neeman's Cotton Classics"
		return "Neeman's Wool Joggers"


class Solution:

	def exercise(self, N, M, A, src, dest, X):
		n = N
		m = M
		edges = A
		adj = [[] for i in range(n)]
		for i in edges:
			(n1, n2, wt) = i
			adj[n1].append([n2, wt])
			adj[n2].append([n1, wt])
		import sys
		ans = [sys.maxsize for i in range(n)]
		ans[src] = 0
		from queue import PriorityQueue
		pq = PriorityQueue()
		pq.put([0, src])
		while pq.qsize() != 0:
			(cd, cn) = pq.get()
			for i in adj[cn]:
				(next_node, wt) = i
				if cd + wt < ans[next_node]:
					ans[next_node] = cd + wt
					pq.put([cd + wt, next_node])
		if ans[dest] > X:
			return "Neeman's Wool Joggers"
		return "Neeman's Cotton Classics"


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

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		(d, q, r) = (defaultdict(list), [[0, src]], [float('inf')] * N)
		for (i, j, k) in A:
			d[i].append([j, k])
			d[j].append([i, k])
		heapify(q)
		while q:
			(dis, node) = heappop(q)
			if dis > r[node]:
				continue
			r[node] = dis
			for (cnode, cdis) in d[node]:
				heappush(q, [dis + cdis, cnode])
		if r[dest] <= X:
			return "Neeman's Cotton Classics"
		return "Neeman's Wool Joggers"


import heapq
MAX = float('inf')

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		adj = [[] for _ in range(N)]
		for (u, v, w) in A:
			adj[u].append([v, w])
			adj[v].append([u, w])
		d = [MAX] * N
		d[src] = 0
		pq = [[0, src]]
		heapq.heapify(pq)
		while pq:
			u = heapq.heappop(pq)[1]
			for (i, w) in adj[u]:
				if d[i] > w + d[u]:
					d[i] = w + d[u]
					heapq.heappush(pq, [d[i], i])
		if d[dest] == MAX:
			return -1
		elif d[dest] > X:
			return "Neeman's Wool Joggers"
		else:
			return "Neeman's Cotton Classics"


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

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		(d, q, r) = (defaultdict(list), [[0, src]], [float('inf')] * N)
		for (i, j, k) in A:
			d[i].append([j, k])
			d[j].append([i, k])
		heapify(q)
		while q:
			(dis, node) = heappop(q)
			if dis > r[node]:
				continue
			r[node] = dis
			for (cnode, cdis) in d[node]:
				heappush(q, [dis + cdis, cnode])
		if r[dest] <= X:
			return "Neeman's Cotton Classics"
		return "Neeman's Wool Joggers"
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M, src, dest, X) = map(int, input().split())
		A = [[0] * 3 for i in range(M)]
		for i in range(M):
			(a, b, c) = map(int, input().split())
			A[i][0] = a
			A[i][1] = b
			A[i][2] = c
		ob = Solution()
		print(ob.exercise(N, M, A, src, dest, X))


import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		ans = [float('inf') for i in range(N)]
		ans[src] = 0
		graph = {i: [] for i in range(N)}
		for (a, b, c) in A:
			graph[a].append([b, c])
			graph[b].append([a, c])
		queue = []
		heapq.heapify(queue)
		heapq.heappush(queue, [0, src])
		while queue:
			(wt, node) = heapq.heappop(queue)
			for (adj_node, adj_node_wt) in graph[node]:
				if adj_node_wt + wt < ans[adj_node]:
					ans[adj_node] = adj_node_wt + wt
					heapq.heappush(queue, [ans[adj_node], adj_node])
		t = ans[dest]
		if t > X:
			return "Neeman's Wool Joggers"
		else:
			return "Neeman's Cotton Classics"


class Solution:

	def exercise(self, n, m, pp, s, dest, x):
		ans = [float('inf') for _ in range(n)]
		ans[s] = 0
		l = {i: [] for i in range(n)}
		for (a, b, c) in pp:
			l[a].append([b, c])
			l[b].append([a, c])
		from heapq import heapify, heappop, heappush
		h = []
		heapify(h)
		heappush(h, (0, s))
		while h:
			(wt, node) = heappop(h)
			for (child, dis) in l[node]:
				if ans[child] > dis + wt:
					ans[child] = dis + wt
					heappush(h, (dis + wt, child))
		t = ans[dest]
		if t > x:
			return "Neeman's Wool Joggers"
		else:
			return "Neeman's Cotton Classics"


from heapq import *

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		dist = [float('inf')] * N
		visited = set()
		heap = [(0, src)]
		dist[src] = 0
		dic = {i: [] for i in range(N)}
		for a in A:
			dic[a[0]].append((a[1], a[2]))
			dic[a[1]].append((a[0], a[2]))
		while heap:
			(d, n) = heappop(heap)
			if n in visited:
				continue
			visited.add(n)
			for (i, c) in dic[n]:
				dist[i] = min(dist[i], d + c)
				heappush(heap, (dist[i], i))
		if dist[dest] <= X:
			return "Neeman's Cotton Classics"
		else:
			return "Neeman's Wool Joggers"
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M, src, dest, X) = map(int, input().split())
		A = [[0] * 3 for i in range(M)]
		for i in range(M):
			(a, b, c) = map(int, input().split())
			A[i][0] = a
			A[i][1] = b
			A[i][2] = c
		ob = Solution()
		print(ob.exercise(N, M, A, src, dest, X))


from heapq import *

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		dist = [float('inf')] * N
		visited = set()
		heap = [(0, src)]
		dist[src] = 0
		dic = {i: [] for i in range(N)}
		for a in A:
			dic[a[0]].append((a[1], a[2]))
			dic[a[1]].append((a[0], a[2]))
		while heap:
			(d, n) = heappop(heap)
			if n in visited:
				continue
			visited.add(n)
			for (i, c) in dic[n]:
				dist[i] = min(dist[i], d + c)
				heappush(heap, (dist[i], i))
		if dist[dest] <= X:
			return "Neeman's Cotton Classics"
		else:
			return "Neeman's Wool Joggers"


import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		graph = {}
		visited = [False for i in range(N)]
		for i in A:
			(s, d, w) = (i[0], i[1], i[2])
			if s not in graph:
				graph[s] = [[d, w]]
			else:
				graph[s].append([d, w])
			if d not in graph:
				graph[d] = [[s, w]]
			else:
				graph[d].append([s, w])
		q = []
		q.append([0, src])
		heapq.heapify(q)
		while q:
			curr = heapq.heappop(q)
			(dist, src) = curr
			if visited[src] == False:
				visited[src] = True
				if src == dest:
					if dist > X:
						return "Neeman's Wool Joggers"
					else:
						return "Neeman's Cotton Classics"
				for i in graph[src]:
					if visited[i[0]] == False:
						heapq.heappush(q, [dist + i[1], i[0]])


import collections
import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		adj = collections.defaultdict(list)
		for (u, v, w) in A:
			adj[u].append((v, w))
			adj[v].append((u, w))
		dist = [float('inf')] * N
		vis = [False] * N
		dist[src] = 0
		vis[src] = True
		heap = [(0, src)]
		while heap:
			(curr_dist, curr_vertex) = heapq.heappop(heap)
			for (nei, weight) in adj[curr_vertex]:
				if dist[nei] > weight + curr_dist:
					dist[nei] = weight + curr_dist
					heapq.heappush(heap, (weight + curr_dist, nei))
		src_dst_d = dist[dest] - dist[src]
		if src_dst_d <= X:
			return "Neeman's Cotton Classics"
		else:
			return "Neeman's Wool Joggers"


from collections import defaultdict
import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		adj = defaultdict(list)
		for (n1, n2, w2) in A:
			adj[n1].append((n2, w2))
			adj[n2].append((n1, w2))
		min_heap = [(0, src)]
		visited = set()
		distance = [float('inf')] * N
		distance[src] = 0
		while min_heap:
			(w1, n1) = heapq.heappop(min_heap)
			visited.add(n1)
			if n1 == dest:
				if w1 > X:
					return "Neeman's Wool Joggers"
				else:
					return "Neeman's Cotton Classics"
			for (n2, w2) in adj[n1]:
				if n2 not in visited:
					if distance[n2] > w1 + w2:
						distance[n2] = w1 + w2
						heapq.heappush(min_heap, [w1 + w2, n2])
		return -1


class Solution:

	def exercise(self, N, M, A, src, dest, X):
		import heapq
		q = []
		heapq.heapify(q)
		heapq.heappush(q, [0, src])
		vis = [0] * N
		adj = [[] for i in range(N)]
		for i in range(M):
			a1 = A[i][0]
			a2 = A[i][1]
			a3 = A[i][2]
			adj[a1].append([a2, a3])
			adj[a2].append([a1, a3])
		while len(q) > 0:
			p = heapq.heappop(q)
			x = p[0]
			y = p[1]
			if y == dest:
				if x <= X:
					return "Neeman's Cotton Classics"
				else:
					return "Neeman's Wool Joggers"
			if vis[y] == 1:
				continue
			vis[y] = 1
			for i in adj[y]:
				heapq.heappush(q, [i[1] + x, i[0]])
		return ''


class Solution:

	def exercise(self, N, M, A, src, dest, X):
		graph = [[] for i in range(N + 1)]
		inf = float('inf')
		dist = [inf for i in range(N + 1)]
		dist[src] = 0
		for k in A:
			(x, y, d) = k
			graph[x].append((y, d))
			graph[y].append((x, d))
		import heapq
		heap = [(0, src)]
		while heap:
			(d, a) = heapq.heappop(heap)
			if a == dest:
				break
			for k in graph[a]:
				(y, h) = k
				if dist[y] > h + d:
					dist[y] = h + dist[a]
					heapq.heappush(heap, (h + d, y))
		if d <= X:
			return "Neeman's Cotton Classics"
		else:
			return "Neeman's Wool Joggers"


class Solution:

	def exercise(self, N, M, A, src, dest, X):
		graph = [[] for i in range(N + 1)]
		inf = float('inf')
		dist = [inf for i in range(N + 1)]
		dist[src] = 0
		for k in A:
			(x, y, d) = k
			graph[x].append((y, d))
			graph[y].append((x, d))
		import collections
		deq = collections.deque([src])
		while deq:
			a = deq.popleft()
			for k in graph[a]:
				(y, h) = k
				if dist[y] > h + dist[a]:
					dist[y] = h + dist[a]
					deq.append(y)
		if dist[dest] <= X:
			return "Neeman's Cotton Classics"
		else:
			return "Neeman's Wool Joggers"


import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		graph = [[] for i in range(N)]
		for a in A:
			graph[a[0]].append((a[1], a[2]))
			graph[a[1]].append((a[0], a[2]))
		req_dist = -1
		heap = [(0, src)]
		min_dist = [-1 for i in range(N)]
		min_dist[src] = 0
		while heap:
			(d, node) = heapq.heappop(heap)
			if node == dest:
				req_dist = d
				break
			flag = False
			for (child, d_) in graph[node]:
				if min_dist[child] == -1:
					min_dist[child] = d + d_
					heapq.heappush(heap, (d + d_, child))
				elif min_dist[child] > d + d_:
					min_dist[child] = d + d_
					heapq.heappush(heap, (d + d_, child))
			if flag:
				break
		if req_dist <= X:
			return "Neeman's Cotton Classics"
		return "Neeman's Wool Joggers"


import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		dist = [float('inf')] * N
		dist[src] = 0
		graph = [[] for _ in range(N)]
		visited = set()
		for (u, v, w) in A:
			graph[u].append((v, w))
			graph[v].append((u, w))

		def djks(src):
			heap = [(0, src)] + [(float('inf'), i) for i in range(N) if i != src]
			while heap:
				(dis, u) = heapq.heappop(heap)
				if u == dest:
					return dis
				visited.add(u)
				for (v, w) in graph[u]:
					if v not in visited and dis + w < dist[v]:
						dist[v] = dis + w
						heapq.heappush(heap, (dist[v], v))
			return -1
		ans = djks(src)
		return "Neeman's Wool Joggers" if ans > X else "Neeman's Cotton Classics"


import sys
import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		adj = [[] for i in range(N)]
		visited = set()
		for i in A:
			adj[i[0]].append([i[1], i[2]])
			adj[i[1]].append([i[0], i[2]])
		inf = sys.maxsize
		dp = [inf] * N
		dp[src] = 0
		h = [(dp[src], src)]
		for _ in range(N):
			(node_dis, mnode) = heapq.heappop(h)
			if mnode in visited:
				continue
			visited.add(mnode)
			for i in adj[mnode]:
				if i[0] in visited:
					continue
				if dp[i[0]] > dp[mnode] + i[1]:
					dp[i[0]] = dp[mnode] + i[1]
					heapq.heappush(h, (dp[i[0]], i[0]))
		if dp[dest] > X:
			return "Neeman's Wool Joggers"
		else:
			return "Neeman's Cotton Classics"


import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		adj = [[] for i in range(N)]
		for i in range(M):
			(v, u, w) = A[i]
			adj[v].append((u, w))
			adj[u].append((v, w))
		visited = [False] * N
		dist = [float('inf')] * N
		min_heap = []
		heapq.heappush(min_heap, (0, src))
		dist[src] = 0
		while min_heap:
			(d, v) = heapq.heappop(min_heap)
			if v == dest:
				if d <= X:
					return "Neeman's Cotton Classics"
				else:
					return "Neeman's Wool Joggers"
			if visited[v]:
				continue
			visited[v] = True
			for pair in adj[v]:
				(u, u_d) = pair
				if visited[u] or d + u_d >= dist[u]:
					continue
				dist[u] = d + u_d
				heapq.heappush(min_heap, (dist[u], u))
		return ''


import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		dist = [float('inf') for i in range(N + 1)]
		dist[src] = 0
		adj = {}
		for x in range(N + 1):
			adj[x] = []
		for [u, v, dis] in A:
			adj[u].append((v, dis))
			adj[v].append((u, dis))
		pq = [(0, src)]
		heapq.heapify(pq)
		while len(pq):
			(dis_u, u) = heapq.heappop(pq)
			if dis_u > dist[u]:
				continue
			for (v, dis_v) in adj[u]:
				if dist[u] + dis_v < dist[v]:
					dist[v] = dist[u] + dis_v
					heapq.heappush(pq, (dist[v], v))
		if dist[dest] <= X:
			return "Neeman's Cotton Classics"
		else:
			return "Neeman's Wool Joggers"


import heapq

class Solution:

	def exercise(self, N, M, A, src, dest, X):
		q = []
		dist = [float('inf')] * N
		dist[src] = 0
		adj = [[] for _ in range(N)]
		for (i, j, w) in A:
			adj[i].append([j, w])
			adj[j].append([i, w])
		heapq.heappush(q, [0, src])
		while q:
			(w, v) = q.pop(0)
			for neigh in adj[v]:
				if dist[v] + neigh[1] < dist[neigh[0]]:
					dist[neigh[0]] = dist[v] + neigh[1]
					heapq.heappush(q, [dist[neigh[0]], neigh[0]])
		if dist[dest] > X:
			return "Neeman's Wool Joggers"
		else:
			return "Neeman's Cotton Classics"