Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Bearland consists of N cities, numbered 1 through N.
Cities are connected with bidirectional roads.

Cities 1 through K were built a long time ago, when citizens liked order and regularity.
Each pair of those old cities is connected with a road of length X.
Note that this description generates K*(K-1)/2 roads.

There are M newer roads, not necessarily of the same lengths.
The i-th of them connects cities a_{i} and b_{i} and has length c_{i}.

There is no road that connects a city to itself.
All M+K*(K-1)/2 roads are distinct (ie. no two of them connects the same pair of cities).
It's guaranteed that it's possible to get from every city to every other city, using one or more roads.

Limak, a bear, lives in the city S.
In order to plan a trip to some other city, for every city he wants to know how quickly he can get there.
Can you help him and find the distance from S to every city?

The distance between two cities is the minimum total length of a path (sequence of roads) between the two cities.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains five integers N, K, X, M and S, denoting the number of cities, the number of old cities, the length of a road between every two old cities, the number of newer roads, and the city where Limak lives, respectively.

Each of the following M lines contains three integers a_{i}, b_{i} and c_{i}, denoting a road of length c_{i} between cities a_{i} and b_{i}.

As guaranteed above: no two cities are connected with more than one road, no road connects a city to itself, and it's possible to get from every city to every other city.

------ Output ------ 

For each test case, output a single line containing N integers.
The i-th of them should denote the distance from the city S to the city i.
The distance from S to S is simply 0.

------ Constraints ------ 

$1 ≤ T ≤ 3$
$2 ≤ K ≤ N ≤ 10^{5}$
$0 ≤ M ≤ 10^{5}$
$1 ≤ S, a_{i}, b_{i} ≤ N$
$1 ≤ X, c_{i} ≤ 10^{9}$

------ Subtasks ------ 

$Subtask #1 (45 points): 2 ≤ K ≤ 500$
$Subtask #2 (55 points): Original constraints.$

----- Sample Input 1 ------ 
3
5 4 100 2 3
1 5 50
5 3 160
5 4 100 2 3
1 5 50
5 3 140
8 3 15 7 5
3 4 10
4 5 20
5 6 10
6 1 7
3 7 1000
7 8 50
3 5 1000000000
----- Sample Output 1 ------ 
100 100 0 100 150 
100 100 0 100 140 
17 32 30 20 0 10 1030 1080
----- explanation 1 ------ 
Test case 1. There are N = 5 cities. The first K = 4 of them are all connected with each other with roads of length X = 100. There are M = 2 extra roads:

Cities 1 and 5 are connected with a road of length 50.
Cities 5 and 3 are connected with a road of length 160.

We are asked to compute distances to all cities from the city S = 3.
Note that the distance from a city to itself is 0, and this is why the third number in the ouput is 0.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Starter code:

Solutions:
from heapq import *
t = int(input())
for _ in range(t):
	(n, k, x, m, s) = map(int, input().split())
	adj = [set() for i in range(n + 1)]
	dist = [float('inf') for i in range(n + 1)]
	if s <= k:
		for __ in range(m):
			(a, b, c) = map(int, input().split())
			adj[a - 1].add((b - 1, c))
			adj[b - 1].add((a - 1, c))
		for i in range(k):
			if i != s - 1:
				adj[i].add((s - 1, x))
				adj[s - 1].add((i, x))
		for i in range(n):
			if i < k:
				dist[i] = x
		vis = [0] * n
		heap = [[0, s - 1]]
		dist[s - 1] = 0
		while heap:
			no = heappop(heap)
			if vis[no[1]] == 1:
				continue
			vis[no[1]] = 1
			for i in adj[no[1]]:
				if dist[i[0]] >= i[1] + no[0]:
					dist[i[0]] = i[1] + no[0]
					heappush(heap, [dist[i[0]], i[0]])
		mi = min([dist[i] for i in range(k)])
		for i in range(k):
			dist[i] = min(dist[i], mi + x)
		print(*dist[:-1])
	else:
		x *= 2
		vis = [0] * (n + 1)
		for i in range(k):
			adj[i].add((n, x // 2))
			adj[n].add((i, x // 2))
		for __ in range(m):
			(a, b, c) = map(int, input().split())
			adj[a - 1].add((b - 1, c * 2))
			adj[b - 1].add((a - 1, c * 2))
		heap = [[0, s - 1]]
		dist[s - 1] = 0
		while heap:
			no = heappop(heap)
			if vis[no[1]] == 1:
				continue
			vis[no[1]] = 1
			for i in adj[no[1]]:
				if dist[i[0]] >= i[1] + no[0]:
					dist[i[0]] = i[1] + no[0]
					heappush(heap, [dist[i[0]], i[0]])
		ma = min([dist[i] for i in range(k)])
		for i in range(k):
			dist[i] = min(dist[i], ma + x)
		print(*[i // 2 for i in dist[:-1]])


import heapq
for _ in range(int(input())):
	(n, k, x, c, start) = map(int, input().split())
	start -= 1
	a = []
	for i in range(n + 1):
		a.append([{}, 0, 1000000000000.0])
	for i in range(k):
		a[i][0][n] = x / 2
		a[n][0][i] = x / 2
	for i in range(c):
		(a1, b1, c1) = map(int, input().split())
		a[a1 - 1][0][b1 - 1] = c1
		a[b1 - 1][0][a1 - 1] = c1
	a[start][2] = 0
	h = [(0, start)]
	heapq.heapify(h)
	while h != []:
		node = heapq.heappop(h)
		if a[node[1]][1] == 0:
			temp = a[node[1]][0]
			for i in temp.keys():
				if a[i][1] == 0:
					heapq.heappush(h, (node[0] + temp[i], i))
					if node[0] + temp[i] < a[i][2]:
						a[i][2] = node[0] + temp[i]
			a[node[1]][1] = 1
	for i in range(n):
		print(int(a[i][2]), end=' ')
	print('')


from collections import defaultdict
import heapq

class Graph:

	def __init__(self):
		self.node = set()
		self.edges = defaultdict(list)
		self.distance = {}

	def addNode(self, value):
		self.node.add(value)

	def addEdges(self, node1, node2, distance):
		self.edges[node1].append(node2)
		self.edges[node2].append(node1)
		self.distance[node1, node2] = distance
		self.distance[node2, node1] = distance

def dijkastra(graph, source, size):
	h = []
	dist = [10 ** 18] * (size + 2)
	dist[source] = 0
	heapq.heappush(h, (0, source))
	while h:
		(d, u) = heapq.heappop(h)
		if dist[u] < d:
			continue
		for i in graph.edges[u]:
			if dist[u] + graph.distance[i, u] < dist[i]:
				dist[i] = dist[u] + graph.distance[i, u]
				heapq.heappush(h, (dist[i], i))
	return dist
t = int(input())
for i in range(t):
	g = Graph()
	(n, k, x, m, s) = [int(x) for x in input().split()]
	for i in range(1, k + 1):
		g.addNode(i)
		g.addNode(n + 1)
		g.addEdges(i, n + 1, x)
	for j in range(m):
		(n1, n2, dist) = [int(x) for x in input().split()]
		g.addNode(n1)
		g.addNode(n2)
		g.addEdges(n1, n2, dist * 2)
	dist = dijkastra(g, s, n)
	print(' '.join([str(int(x / 2)) for x in dist[1:n + 1]]))


import heapq

def solve():
	T = int(input())
	for t in range(T):
		(N, K, X, M, S) = map(int, input().split(' '))
		adj_list = [[] for i in range(N + 1)]
		for i in range(1, K + 1):
			adj_list[0].append((i, X))
			adj_list[i].append((0, 0))
		for i in range(M):
			(a, b, c) = map(int, input().split(' '))
			adj_list[a].append((b, c))
			adj_list[b].append((a, c))
		dist = [10 ** 18 for i in range(N + 1)]
		heap = []
		heapq.heappush(heap, (0, S))
		dist[S] = 0
		while len(heap) > 0:
			tup = heap[0]
			u = tup[1]
			heapq.heappop(heap)
			for (v, weight) in adj_list[u]:
				if dist[v] > dist[u] + weight:
					dist[v] = dist[u] + weight
					heapq.heappush(heap, (dist[v], v))
		print(*dist[1:])
solve()


import heapq

def dijkstra(g, s):
	dist = [10 ** 18] * len(g)
	dist[s] = 0
	pq = [(0, s)]
	while pq:
		(d, u) = heapq.heappop(pq)
		if dist[u] < d:
			continue
		for (v, w) in g[u]:
			alt = d + w
			if alt < dist[v]:
				dist[v] = alt
				heapq.heappush(pq, (alt, v))
	return dist
for t in range(int(input())):
	(N, K, X, M, S) = map(int, input().split())
	g = [[] for i in range(N + 1)]
	for i in range(1, K + 1):
		g[0].append((i, X))
		g[i].append((0, 0))
	for i in range(M):
		(a, b, c) = map(int, input().split())
		g[a].append((b, c))
		g[b].append((a, c))
	dist = dijkstra(g, S)
	print(*dist[1:])


from sys import stdin, maxsize
from heapq import heappop, heappush, heapify

def dijkstra(G, s, k, X):
	heap = [(0, s)]
	heapify(heap)
	visited = set()
	dist = [maxsize] * len(G)
	dist[s] = 0
	done = False
	while len(heap) > 0:
		(d, c) = heappop(heap)
		if c in visited:
			continue
		dist[c] = d
		visited.add(c)
		if c <= K and (not done):
			done = True
			for i in range(1, K + 1):
				heappush(heap, (d + X, i))
		for (n, x) in G[c]:
			if not n in visited:
				heappush(heap, (d + x, n))
	return dist
T = int(stdin.readline())
for t in range(T):
	[N, K, X, M, S] = [int(x) for x in stdin.readline().split()]
	G = [set()] + [set() for _ in range(N)]
	for _ in range(M):
		[a, b, c] = [int(x) for x in stdin.readline().split()]
		G[a].add((b, c))
		G[b].add((a, c))
	distanceToS = dijkstra(G, S, K, X)
	print(' '.join([str(x) for x in distanceToS[1:]]))


from heapq import *
INFINITY = 10 ** 18
for _ in range(int(input())):
	(N, K, X, M, S) = [int(x) for x in input().split()]
	G = [[] for _ in range(N + 1)]
	for _ in range(M):
		(a, b, c) = [int(x) for x in input().split()]
		G[a].append((b, c))
		G[b].append((a, c))
	visited = [False] * (N + 1)
	distance = [INFINITY] * (N + 1)
	distance[S] = 0
	Q = [(0, S)]
	visited_old_cities = False
	while Q:
		(_, u) = heappop(Q)
		visited[u] = True
		if not visited_old_cities and u <= K:
			visited_old_cities = True
			for v in range(1, K + 1):
				if u == v:
					continue
				alt = distance[u] + X
				if alt < distance[v]:
					distance[v] = alt
					heappush(Q, (alt, v))
		for (v, c) in G[u]:
			if visited[v]:
				continue
			alt = distance[u] + c
			if alt < distance[v]:
				distance[v] = alt
				heappush(Q, (alt, v))
	print(' '.join((str(x) for x in distance[1:])))


from collections import defaultdict
from heapq import *

def dijkstra(s, dist, g):
	(q, seen) = ([(0, s)], set())
	while q:
		(cost, v1) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			dist[v1] = cost
			for (c, v2) in g[v1]:
				if v2 not in seen:
					heappush(q, (cost + c, v2))
t = int(input())
while t:
	t -= 1
	(n, k, x, m, s) = map(int, input().split())
	g = [[] for i in range(n + 1)]
	dist = [-1 for i in range(n + 1)]
	for i in range(1, k + 1):
		g[0].append((x / 2, i))
		g[i].append((x / 2, 0))
	for i in range(m):
		(a, b, c) = map(int, input().split())
		g[a].append((c, b))
		g[b].append((c, a))
	out = []
	if s <= k:
		dijkstra(s, dist, g)
		for i in range(k + 1):
			out.append(dist[i])
		for i in range(k + 1, n + 1):
			out.append(dist[i])
	else:
		dijkstra(s, dist, g)
		for i in range(n + 1):
			out.append(dist[i])
	print(' '.join(map(str, map(int, out[1:]))))


from collections import defaultdict
import heapq

def dijkstra(adj, cost, initial):
	visited = {initial: 0}
	h = [(0, initial)]
	path = {}
	nodes = set([i for i in range(N + 1)])
	while nodes and h:
		(current_weight, min_node) = heapq.heappop(h)
		try:
			while min_node not in nodes:
				(current_weight, min_node) = heapq.heappop(h)
		except IndexError:
			break
		nodes.remove(min_node)
		for v in adj[min_node]:
			weight = current_weight + cost[min_node, v]
			if v not in visited or weight < visited[v]:
				visited[v] = weight
				heapq.heappush(h, (weight, v))
				path[v] = min_node
	return visited

def handle_case(N, K, X, M, s):
	edges = []
	for i in range(M):
		(n1, n2, c) = [int(x) for x in input().strip().split()]
		edges.append((n1, n2, c))
	adj = defaultdict(list)
	for (l, r, _) in edges:
		adj[l].append(r)
		adj[r].append(l)
	for i in range(1, K + 1):
		adj[i].append(0)
		adj[0].append(i)
	cost = dict()
	for (l, r, c) in edges:
		cost[l, r] = c
		cost[r, l] = c
	for i in range(1, K + 1):
		cost[i, 0] = 0
		cost[0, i] = X
	d = dijkstra(adj, cost, s)
	lst = [0] * N
	for i in range(1, N + 1):
		lst[i - 1] = str(d[i])
	return lst
T = int(input())
for t in range(T):
	(N, K, X, M, s) = [int(x) for x in input().strip().split()]
	res = handle_case(N, K, X, M, s)
	print(' '.join(res))