Read problem statements in [Mandarin Chinese] and [Bengali].

There are N cities (numbered from 1 to N) and M bidirectional roads. The i^{th} of these roads connects the cities A_{i} and B_{i} and has a length of D_{i} Km.

There are only K cities that have a hospital for corona testing. The cost of corona testing may be different in different cities. For each city, we want to know the minimum cost that needs to be spent to test a corona sample. If city you are in contains a hospital and you choose to test in that hospital itself, then the cost incurred is the cost of corona test in that hospital. Otherwise, if you choose to test in a hospital in another city, then an additional transportation cost is also incurred (Assuming Rs.1 per Km).

So from a city i, if you choose to send a sample to city j, then the total cost incurred will be C_{j} + D(i,j). Here C_{j} denotes the cost of corona testing in a hospital situated in city j and D(i,j) denotes the minimum distance between city i and j via some road network.

Output the *minimum* money that should be spent by a person in each of the N cities for testing a corona sample.

It is guaranteed that there is a path from every city to every other city. Also, there is at most one road between any pair of cities (i.e. no multiple edges). There are no roads from one city to itself (i.e. no self-loops).

Note: Since the inputs and outputs are large, prefer using fast input-output methods.

------ Input Format ------ 

- The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
- Each testcase contains K + M + 1 lines of input.
- The first line of each test case contains three space-separated integers N, M, K.
- K  lines follow. For each valid i, the i^{th} of these lines contains two space-separated integers x_{i}, C_{i} which denotes that there is a hospital in the x_{i}^{th} city and the cost of corona testing in that hospital is C_{i}. There is at most one hospital in a city i.e. all x_{i}-s are distinct.
- Next M lines follow. For each valid i, the i^{th} of these lines contains three space-separated integers A_{i}, B_{i}, D_{i}, which denotes that there is a bidirectional road between City A_{i} and City B_{i} of length D_{i} Km.

------ Output Format ------ 

For each test case, print a single line containing N space-separated integers, where the i^{th} integer denotes the minimum cost of corona testing if you are in the i^{th} city.

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

$1 ≤ T ≤ 4000$
$2 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ M ≤ 4 \cdot 10^{5}$
$1 ≤ K ≤ N$
$1 ≤ x_{i}, A_{i}, B_{i} ≤ N$ for each valid $i$
$1 ≤ C_{i} ≤ 10^{9}$ for each valid $i$
$1 ≤ D_{i} ≤ 10^{9}$ for each valid $i$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$ 
- Sum of $M$ over all test cases does not exceed $4 \cdot 10^{5}$ 
- All $x_{i}$-s in a testcase are distinct.
- It is guaranteed that there is a path from every city to every other city.
- It is guaranteed that there are no self loops and multiple edges.

----- Sample Input 1 ------ 
2
3 2 2
1 5
2 10
1 2 6
2 3 9
3 2 2
1 5
2 10
1 2 1
2 3 9

----- Sample Output 1 ------ 
5 10 19 
5 6 15 

----- explanation 1 ------ 
Test case $1$: The hospitals are situated at cities $1$ and $2$ with their costs being $5$ and 10 respectively. For city $1$ it is optimal to test the sample in its own hospital bearing a total cost of $5$. For city $2$ it is again optimal to test the sample in its own hospital bearing a total cost of $10$. For city $3$ it is optimal to test the sample in the hospital at city $2$ which incurs the traveling cost of $9$ and hospital cost of $10$, so the total cost is $10+9=19$.

Test case $2$: For city $2$, it is optimal to test the sample in hospital at city $1$ which incurs a traveling cost of $1$ and hospital cost of $5$, so the total cost is $1+5=6$.

Difficulty: VERY_HARD
Tags: Graph algorithms

Shortest paths

Starter code:

Solutions:
import heapq
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	ans = [float('infinity')] * (n + 1)
	g = [[] for _ in range(n + 1)]
	h = []
	for _ in range(k):
		(v, d) = map(int, input().split())
		ans[v] = d
		heapq.heappush(h, (d, v))
	for _ in range(m):
		(u, v, d) = map(int, input().split())
		g[u].append((v, d))
		g[v].append((u, d))
	while h:
		(d, u) = heapq.heappop(h)
		for (v, w) in g[u]:
			if ans[v] > ans[u] + w:
				ans[v] = ans[u] + w
				heapq.heappush(h, (ans[v], v))
	print(' '.join(map(str, ans[1:])))


from heapq import *
from collections import *
import sys
mod = 1000000007
INF = float('inf')
for _ in range(int(sys.stdin.readline())):
	(n, m, k) = map(int, sys.stdin.readline().split())
	d = defaultdict(list)
	for i in range(k):
		(a, b) = map(int, sys.stdin.readline().split())
		d[a].append((0, b))
		d[0].append((a, b))
	for i in range(m):
		(a, b, c) = map(int, sys.stdin.readline().split())
		d[a].append((b, c))
		d[b].append((a, c))
	visited = [0] * (n + 1)
	h = [(0, 0)]
	dist = [INF] * (n + 1)
	dist[0] = 0
	while h:
		(x, y) = heappop(h)
		if visited[y]:
			continue
		visited[y] = 1
		for (p, q) in d[y]:
			if dist[p] > q + x:
				dist[p] = q + x
				heappush(h, (dist[p], p))
	print(*dist[1:])


import heapq
T = int(input())

def solve(N, hos, adj):
	M_dist = [float('inf')] * (N + 1)
	h = []
	for (i, C) in hos:
		heapq.heappush(h, (C, i))
	while h:
		(dist, city) = heapq.heappop(h)
		if dist >= M_dist[city]:
			continue
		M_dist[city] = dist
		for (nei, w) in adj[city]:
			if M_dist[nei] > dist + w:
				heapq.heappush(h, (dist + w, nei))
	ans = []
	for i in range(1, N + 1):
		ans.append(M_dist[i])
	return ans
for _ in range(T):
	(N, M, K) = [int(s) for s in input().split()]
	hos = []
	adj = {}
	for _ in range(K):
		hos.append(tuple((int(s) for s in input().split())))
	for _ in range(M):
		(A, B, D) = [int(s) for s in input().split()]
		if A not in adj:
			adj[A] = []
		if B not in adj:
			adj[B] = []
		adj[A].append((B, D))
		adj[B].append((A, D))
	ans = solve(N, hos, adj)
	for num in ans:
		print(num, end=' ')
	print()


from collections import deque
import heapq

def dijkastra(graph, hospital, dis):
	heap = []
	for (k, v) in hospital.items():
		heap.append((v, k))
		dis[k] = v
	heapq.heapify(heap)
	while heap:
		(d, node) = heapq.heappop(heap)
		for (child, w) in graph[node]:
			nd = d + w
			if nd < dis[child]:
				dis[child] = nd
				heapq.heappush(heap, (nd, child))
t = int(input())
for _ in range(t):
	(n, m, k) = list(map(int, input().split()))
	hospital = {}
	for _ in range(k):
		(a, c) = list(map(int, input().split()))
		hospital[a - 1] = c
	graph = [[] for _ in range(n)]
	for _ in range(m):
		(a, b, w) = list(map(int, input().split()))
		graph[a - 1].append((b - 1, w))
		graph[b - 1].append((a - 1, w))
	inf = float('inf')
	dis = [inf] * n
	dijkastra(graph, hospital, dis)
	print(*dis)


import heapq
import sys
import os
from collections import defaultdict

def dijkstra(graph, source, distance_to_hospital):
	heap = [(source, distance_to_hospital[source])]
	while heap:
		(city, cost) = heapq.heappop(heap)
		for (connected_city, distance) in graph[city]:
			if distance_to_hospital[connected_city] > distance + cost:
				distance_to_hospital[connected_city] = distance + cost
				heapq.heappush(heap, (connected_city, distance_to_hospital[connected_city]))
for _ in range(int(input())):
	(N, M, K) = map(int, input().split())
	graph = defaultdict(list)
	distance_to_hospital = [sys.maxsize for _ in range(N + 1)]
	distance_to_hospital[0] = 0
	for _ in range(K):
		(city, cost) = map(int, input().split())
		graph[city].append((0, cost))
		graph[0].append((city, cost))
	for _ in range(M):
		(u, v, distance) = map(int, input().split())
		graph[u].append((v, distance))
		graph[v].append((u, distance))
	dijkstra(graph, 0, distance_to_hospital)
	print(*distance_to_hospital[1:])


from collections import *
from heapq import *
t = int(input())
for _ in range(t):
	d = defaultdict(list)
	(n, m, k) = map(int, input().split())
	for i in range(k):
		(x, c) = map(int, input().split())
		d[0].append((x, c))
		d[x].append((0, c))
	for i in range(m):
		(a, b, c) = map(int, input().split())
		d[a].append((b, c))
		d[b].append((a, c))
	dist = [float('inf')] * (n + 1)
	dist[0] = 0
	h = [(0, 0)]
	visited = [0] * (n + 1)
	while h:
		(a, b) = heappop(h)
		if visited[b]:
			continue
		visited[b] = 1
		for (x, y) in d[b]:
			if dist[x] > a + y:
				dist[x] = a + y
				heappush(h, (dist[x], x))
	print(*dist[1:])


from collections import defaultdict
import sys
import heapq

def dijkstra(graph, start, dist):
	queue = [(start, dist[start])]
	while queue:
		(ele, w) = heapq.heappop(queue)
		for (adjele, weight) in graph[ele]:
			if dist[adjele] > w + weight:
				dist[adjele] = w + weight
				heapq.heappush(queue, (adjele, dist[adjele]))
for _ in range(int(input())):
	(N, M, K) = [int(x) for x in input().split()]
	hosp = {}
	graph = defaultdict(list)
	dist = [sys.maxsize for _ in range(N + 1)]
	dist[0] = 0
	for _ in range(K):
		(i, c) = [int(x) for x in input().split()]
		graph[i].append((0, c))
		graph[0].append((i, c))
	for _ in range(M):
		(i, j, d) = [int(x) for x in input().split()]
		graph[i].append((j, d))
		graph[j].append((i, d))
	dijkstra(graph, 0, dist)
	print(*dist[1:])


from sys import stdin
from collections import defaultdict
import heapq
t = int(stdin.readline())
for _ in range(t):
	(n, m, k) = map(int, stdin.readline().split())
	hos = []
	for i in range(k):
		(x, c) = map(int, stdin.readline().split())
		hos.append((c, x))
	graph = defaultdict(list)
	for i in range(m):
		(a, b, d) = map(int, stdin.readline().split())
		graph[a].append((b, d))
		graph[b].append((a, d))
	heapq.heapify(hos)
	dic = {}
	while len(dic) < n:
		(cost, cit) = heapq.heappop(hos)
		if cit not in dic:
			dic[cit] = cost
			for nbour in graph[cit]:
				dist = nbour[1]
				heapq.heappush(hos, (cost + dist, nbour[0]))
	ans = []
	for i in range(1, n + 1):
		ans.append(dic[i])
	print(*ans)


from heapq import *
import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, m, k) = mp()
	d = defaultdict(list)
	for i in range(k):
		(a, b) = mp()
		d[a].append((0, b))
		d[0].append((a, b))
	for i in range(m):
		(a, b, c) = mp()
		d[a].append((b, c))
		d[b].append((a, c))
	visited = [0] * (n + 1)
	h = [(0, 0)]
	dist = [INF] * (n + 1)
	dist[0] = 0
	while h:
		(x, y) = heappop(h)
		if visited[y]:
			continue
		visited[y] = 1
		for (p, q) in d[y]:
			if dist[p] > q + x:
				dist[p] = q + x
				heappush(h, (dist[p], p))
	print(*dist[1:])
for _ in range(inp()):
	solve()


import heapq
import sys
input = sys.stdin.readline
INF = 999999999999999
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for _ in range(k):
		(xi, ci) = map(int, input().split())
		adj[0].append([xi, ci])
		adj[xi].append([0, ci])
	for _ in range(m):
		(a, b, d) = map(int, input().split())
		adj[a].append([b, d])
		adj[b].append([a, d])
	dis = [INF] * (n + 1)
	source = 0
	dis[source] = 0
	pq = []
	heapq.heappush(pq, (0, source))
	while len(pq):
		(dist, prev) = heapq.heappop(pq)
		for val in adj[prev]:
			nex = val[0]
			newDist = val[1]
			if dis[nex] > dist + newDist:
				dis[nex] = dist + newDist
				heapq.heappush(pq, (dis[nex], nex))
	for i in range(1, n + 1):
		print(dis[i], end=' ')
	print()


import heapq
import sys
input = sys.stdin.readline
INF = 999999999999999
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	adj = [[] for _ in range(n + 1)]
	for _ in range(k):
		(xi, ci) = map(int, input().split())
		adj[0].append([xi, ci])
		adj[xi].append([0, ci])
	for _ in range(m):
		(a, b, d) = map(int, input().split())
		adj[a].append([b, d])
		adj[b].append([a, d])
	dis = [INF] * (n + 1)
	dis[0] = 0
	pq = []
	heapq.heappush(pq, (0, 0))
	while len(pq) > 0:
		(cst, u) = heapq.heappop(pq)
		for val in adj[u]:
			v = val[0]
			dd = val[1]
			if cst + dd < dis[v]:
				dis[v] = cst + dd
				heapq.heappush(pq, (dis[v], v))
	for i in range(1, n + 1):
		print(dis[i], end=' ')
	print()


from sys import stdin
input = stdin.readline
from queue import PriorityQueue

def dijkstra():
	v = [False] * (n + 1)
	while not q.empty():
		(val, p) = q.get()
		if v[p]:
			continue
		v[p] = True
		for x in adj[p]:
			if ans[p] + d[p, x] < ans[x]:
				ans[x] = ans[p] + d[p, x]
				q.put([ans[x], x])
for T in range(int(input())):
	(n, m, k) = map(int, input().split())
	ans = [float('inf')] * (n + 1)
	q = PriorityQueue()
	for i in range(k):
		(x, c) = map(int, input().split())
		q.put([c, x])
		ans[x] = c
	adj = [[] for i in range(n + 1)]
	d = dict()
	for i in range(m):
		(u, v, dis) = map(int, input().split())
		adj[u].append(v)
		adj[v].append(u)
		d[u, v] = dis
		d[v, u] = dis
	dijkstra()
	print(*ans[1:])


from collections import defaultdict
import heapq
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	(costs, neigh) = ([], defaultdict(list))
	for _ in range(k):
		(x, C) = map(int, input().split())
		costs.append((C, x))
	for _ in range(m):
		(a, b, d) = map(int, input().split())
		neigh[a].append((b, d))
		neigh[b].append((a, d))
	heapq.heapify(costs)
	answer = {}
	while len(answer) < n:
		(cost, act) = heapq.heappop(costs)
		if act not in answer:
			answer[act] = cost
			for (vei, d) in neigh[act]:
				heapq.heappush(costs, (cost + d, vei))
	print(*[answer[i] for i in range(1, n + 1)])