Musicians of a popular band "Flayer" have announced that they are going to "make their exit" with a world tour. Of course, they will visit Berland as well.

There are n cities in Berland. People can travel between cities using two-directional train routes; there are exactly m routes, i-th route can be used to go from city v_{i} to city u_{i} (and from u_{i} to v_{i}), and it costs w_{i} coins to use this route.

Each city will be visited by "Flayer", and the cost of the concert ticket in i-th city is a_{i} coins.

You have friends in every city of Berland, and they, knowing about your programming skills, asked you to calculate the minimum possible number of coins they have to pay to visit the concert. For every city i you have to compute the minimum number of coins a person from city i has to spend to travel to some city j (or possibly stay in city i), attend a concert there, and return to city i (if j ≠ i).

Formally, for every $i \in [ 1, n ]$ you have to calculate $\operatorname{min}_{j = 1} 2 d(i, j) + a_{j}$, where d(i, j) is the minimum number of coins you have to spend to travel from city i to city j. If there is no way to reach city j from city i, then we consider d(i, j) to be infinitely large.


-----Input-----

The first line contains two integers n and m (2 ≤ n ≤ 2·10^5, 1 ≤ m ≤ 2·10^5).

Then m lines follow, i-th contains three integers v_{i}, u_{i} and w_{i} (1 ≤ v_{i}, u_{i} ≤ n, v_{i} ≠ u_{i}, 1 ≤ w_{i} ≤ 10^12) denoting i-th train route. There are no multiple train routes connecting the same pair of cities, that is, for each (v, u) neither extra (v, u) nor (u, v) present in input.

The next line contains n integers a_1, a_2, ... a_{k} (1 ≤ a_{i} ≤ 10^12) — price to attend the concert in i-th city.


-----Output-----

Print n integers. i-th of them must be equal to the minimum number of coins a person from city i has to spend to travel to some city j (or possibly stay in city i), attend a concert there, and return to city i (if j ≠ i).


-----Examples-----
Input
4 2
1 2 4
2 3 7
6 20 1 25

Output
6 14 1 25 

Input
3 3
1 2 1
2 3 1
1 3 1
30 10 20

Output
12 10 12

Difficulty: HARD
Tags: Graph algorithms

Data structures

Shortest paths
Skill types: Data structures

Starter code:

Solutions:
from __future__ import division, print_function
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import BytesIO, IOBase

class FastI(object):

	def __init__(self, fd=0, buffersize=2 ** 14):
		self.stream = stream = BytesIO()
		self.bufendl = 0

		def read2buffer():
			curpos = stream.tell()
			s = os.read(fd, buffersize + os.fstat(fd).st_size)
			stream.seek(0, 2)
			stream.write(s)
			stream.seek(curpos)
			return s
		self.read2buffer = read2buffer

	def read(self):
		while self.read2buffer():
			pass
		return self.stream.read() if self.stream.tell() else self.stream.getvalue()

	def readline(self):
		while self.bufendl == 0:
			s = self.read2buffer()
			self.bufendl += s.count(b'\n') + (not s)
		self.bufendl -= 1
		return self.stream.readline()

	def input(self):
		return self.readline().rstrip(b'\r\n')

	def readnumbers(self, n, zero=0):
		conv = ord if py2 else lambda x: x
		A = []
		numb = zero
		sign = 1
		curpos = self.stream.tell()
		self.stream.seek(0, 2)
		buffsize = self.stream.tell()
		self.stream.seek(curpos)
		while len(A) < n:
			if curpos >= buffsize:
				self.read2buffer()
				self.stream.seek(0, 2)
				buffsize = self.stream.tell()
				self.stream.seek(curpos)
				if curpos == buffsize:
					break
			s = self.stream.read(min(64, buffsize - curpos))
			i = 0
			while i < len(s) and len(A) != n:
				if s[i] >= b'0'[0]:
					numb = 10 * numb + (conv(s[i]) - 48)
				elif s[i] != b'\r'[0]:
					if s[i] == b'-'[0]:
						sign = -1
					else:
						A.append(sign * numb)
						numb = zero
						sign = 1
				i += 1
			curpos += i
		if curpos == buffsize and len(A) < n:
			A.append(sign * numb)
		assert len(A) == n
		self.stream.seek(curpos)
		return A

class FastO(IOBase):

	def __init__(self, fd=1):
		stream = BytesIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = stream.write if py2 else lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
input = sys.stdin.readline
big = 3000000000000.0

class segheap:

	def __init__(self, data):
		n = len(data)
		m = 1
		while m < n:
			m *= 2
		self.n = n
		self.m = m
		self.data = [big] * (2 * m)
		for i in range(n):
			self.data[i + m] = data[i]
		for i in reversed(range(m)):
			self.data[i] = min(self.data[2 * i], self.data[2 * i + 1])

	def mini(self):
		i = 1
		while i < self.m:
			if self.data[i] == self.data[2 * i]:
				i = 2 * i
			else:
				i = 2 * i + 1
		i -= self.m
		self.setter(i, big)
		return i

	def setter(self, ind, val):
		ind += self.m
		if val < self.data[ind]:
			while ind > 0 and self.data[ind] > val:
				self.data[ind] = val
				ind //= 2
		elif val > self.data[ind]:
			old_val = self.data[ind]
			self.data[ind] = val
			ind //= 2
			while ind > 0 and self.data[ind] == old_val:
				self.data[ind] = min(self.data[2 * ind], self.data[2 * ind + 1])
				ind //= 2
(n, m) = [int(x) for x in sys.stdin.readline().split()]
inp = sys.stdin.readnumbers(3 * m, 0.0)
coupl = [[] for _ in range(n)]
cost = [[] for _ in range(n)]
for _ in range(m):
	v = int(inp[_ * 3 + 0] - 1)
	u = int(inp[_ * 3 + 1] - 1)
	w = inp[_ * 3 + 2]
	coupl[v].append(u)
	coupl[u].append(v)
	cost[u].append(w)
	cost[v].append(w)
inp = sys.stdin.readnumbers(n, 0.0)
best = [inp[i] for i in range(n)]
Q = segheap(best)
while Q.data[1] != big:
	c = Q.data[1]
	node = Q.mini()
	if best[node] != c:
		continue
	for j in range(len(coupl[node])):
		nei = coupl[node][j]
		C = c + 2 * cost[node][j]
		if C < best[nei]:
			best[nei] = C
			Q.setter(nei, C)
for x in best:
	sys.stdout.write(str(int(x)))
	sys.stdout.write(' ')


import sys
from heapq import heappush, heappop
(n, m) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
adj = [[] for _ in range(n)]
for _ in range(m):
	(v, u, w) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
	adj[v - 1].append((u - 1, w * 2))
	adj[u - 1].append((v - 1, w * 2))
a = list(map(int, sys.stdin.buffer.readline().decode('utf-8').split()))
ans = a[:]
mask = 2 ** 18 - 1
shift = 18
hq = sorted([(a[i] << shift) + i for i in range(n)])
while hq:
	x = heappop(hq)
	(cost, v) = (x >> shift, x & mask)
	if cost > ans[v]:
		continue
	for (u, w) in adj[v]:
		if cost + w < ans[u]:
			ans[u] = cost + w
			heappush(hq, (cost + w << shift) + u)
print(*ans)


import os
import sys
from io import BytesIO

class FastI:

	def __init__(self):
		self.stream = BytesIO()
		self.newlines = 0

	def read(self, b=b'\n'):
		while b:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
		return self.stream.read() if self.stream.tell() else self.stream.getvalue()

	def readline(self, b=b'\n'):
		while b and self.newlines == 0:
			(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			(self.stream.seek(0, 2), self.stream.write(b), self.stream.seek(ptr))
			self.newlines += b.count(b'\n')
		self.newlines -= bool(b)
		return self.stream.readline()

	def readnumber(self, var=int):
		b = self.read()
		A = []
		(num, sign) = (var(0), 1)
		for char in b:
			if char >= b'0'[0]:
				num = 10 * num + char - b'0'[0]
			elif char == b'-'[0]:
				sign = -1
			elif char != b'\r'[0]:
				A.append(sign * num)
				(num, sign) = (var(0), 1)
		if b and b[-1] >= b'0'[0]:
			A.append(sign * num)
		return A

class FastO:

	def __init__(self):
		stream = BytesIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
(input, flush) = (sys.stdin.readline, sys.stdout.flush)
big = 3000000000000.0

class segheap:

	def __init__(self, data):
		n = len(data)
		m = 1
		while m < n:
			m *= 2
		self.n = n
		self.m = m
		self.data = [big] * (2 * m)
		for i in range(n):
			self.data[i + m] = data[i]
		for i in reversed(range(m)):
			self.data[i] = min(self.data[2 * i], self.data[2 * i + 1])

	def mini(self):
		i = 1
		while i < self.m:
			if self.data[i] == self.data[2 * i]:
				i = 2 * i
			else:
				i = 2 * i + 1
		i -= self.m
		self.setter(i, big)
		return i

	def setter(self, ind, val):
		ind += self.m
		if val < self.data[ind]:
			while ind > 0 and self.data[ind] > val:
				self.data[ind] = val
				ind //= 2
		elif val > self.data[ind]:
			old_val = self.data[ind]
			self.data[ind] = val
			ind //= 2
			while ind > 0 and self.data[ind] == old_val:
				self.data[ind] = min(self.data[2 * ind], self.data[2 * ind + 1])
				ind //= 2
inp = sys.stdin.readnumber(float)
ii = 0

def getnext():
	global ii
	a = inp[ii]
	ii += 1
	return a

def getnexts(n):
	global ii
	a = inp[ii:ii + n]
	ii += n
	return a
(n, m) = map(int, getnexts(2))
coupl = [[] for _ in range(n)]
cost = [[] for _ in range(n)]
for _ in range(m):
	v = int(getnext()) - 1
	u = int(getnext()) - 1
	w = getnext()
	coupl[v].append(u)
	coupl[u].append(v)
	cost[u].append(w)
	cost[v].append(w)
best = getnexts(n)
Q = segheap(best)
while Q.data[1] != big:
	c = Q.data[1]
	node = Q.mini()
	if best[node] != c:
		continue
	for j in range(len(coupl[node])):
		nei = coupl[node][j]
		C = c + 2 * cost[node][j]
		if C < best[nei]:
			best[nei] = C
			Q.setter(nei, C)
for x in best:
	sys.stdout.write(str(int(x)))
	sys.stdout.write(' ')


from __future__ import division, print_function
import os
import sys
from io import BytesIO, IOBase
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange

class FastI(object):
	stream = BytesIO()
	newlines = 0
	read = lambda self: self.stream.read() if self._read() or self.stream.tell() else self.stream.getvalue()

	def _read(self, getline=False, s=b'\n'):
		while s and (not (getline and self.newlines)):
			(s, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
			self.newlines += s.count(b'\n')
			self.stream.seek(0, 2)
			self.stream.write(s)
			self.stream.seek(ptr)

	def readline(self):
		self._read(True)
		self.newlines -= 1
		return self.stream.readline()

	def readnumbers(self, n, var=int):
		(A, numb, sign) = ([], var(0), 1)
		ptr = self.stream.tell()
		self.stream.seek(0, 2)
		buffsize = self.stream.tell()
		self.stream.seek(ptr)
		while len(A) < n:
			if ptr >= buffsize:
				(s, _ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
				self.stream.seek(0, 2)
				self.stream.write(s)
				self.stream.seek(_ptr)
				buffsize += len(s)
				if ptr == buffsize:
					break
			(i, s) = (0, self.stream.read(min(32, buffsize - ptr)))
			while i < len(s) and len(A) != n:
				if s[i] >= b'0'[0]:
					numb = 10 * numb + ((ord(s[i]) if py2 else s[i]) - 48)
				elif s[i] != b'\r'[0]:
					if s[i] == b'-'[0]:
						sign = -1
					else:
						A.append(sign * numb)
						(numb, sign) = (var(0), 1)
				i += 1
			ptr += i
		if ptr == buffsize and len(A) < n:
			A.append(sign * numb)
		self.stream.seek(ptr)
		return A

class FastO(IOBase):

	def __init__(self, fd=1):
		stream = BytesIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = stream.write if py2 else lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
input = sys.stdin.readline
big = 3000000000000.0

class segheap:

	def __init__(self, data):
		n = len(data)
		m = 1
		while m < n:
			m *= 2
		self.n = n
		self.m = m
		self.data = [big] * (2 * m)
		for i in range(n):
			self.data[i + m] = data[i]
		for i in reversed(range(m)):
			self.data[i] = min(self.data[2 * i], self.data[2 * i + 1])

	def mini(self):
		i = 1
		while i < self.m:
			if self.data[i] == self.data[2 * i]:
				i = 2 * i
			else:
				i = 2 * i + 1
		i -= self.m
		self.setter(i, big)
		return i

	def setter(self, ind, val):
		ind += self.m
		if val < self.data[ind]:
			while ind > 0 and self.data[ind] > val:
				self.data[ind] = val
				ind //= 2
		elif val > self.data[ind]:
			old_val = self.data[ind]
			self.data[ind] = val
			ind //= 2
			while ind > 0 and self.data[ind] == old_val:
				self.data[ind] = min(self.data[2 * ind], self.data[2 * ind + 1])
				ind //= 2
(n, m) = [int(x) for x in sys.stdin.readline().split()]
inp = sys.stdin.readnumbers(3 * m, float)
coupl = [[] for _ in range(n)]
cost = [[] for _ in range(n)]
for _ in range(m):
	v = int(inp[_ * 3 + 0] - 1)
	u = int(inp[_ * 3 + 1] - 1)
	w = inp[_ * 3 + 2]
	coupl[v].append(u)
	coupl[u].append(v)
	cost[u].append(w)
	cost[v].append(w)
inp = sys.stdin.readnumbers(n, float)
best = [inp[i] for i in range(n)]
Q = segheap(best)
while Q.data[1] != big:
	c = Q.data[1]
	node = Q.mini()
	if best[node] != c:
		continue
	for j in range(len(coupl[node])):
		nei = coupl[node][j]
		C = c + 2 * cost[node][j]
		if C < best[nei]:
			best[nei] = C
			Q.setter(nei, C)
for x in best:
	sys.stdout.write(str(int(x)))
	sys.stdout.write(' ')


from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
graph = [[] for i in range(n + 1)]
for _ in range(m):
	(u, v, w) = map(int, input().split())
	graph[u].append((v, 2 * w))
	graph[v].append((u, 2 * w))
ans = [int(i) for i in input().split()]
heap = [(ans[i], i + 1) for i in range(n)]
heapify(heap)
while heap:
	(dist, node) = heappop(heap)
	if dist > ans[node - 1]:
		continue
	for (child, cost) in graph[node]:
		if ans[child - 1] > dist + cost:
			ans[child - 1] = dist + cost
			heappush(heap, (ans[child - 1], child))
ans = ' '.join(map(str, ans))
sys.stdout.write(ans)


from heapq import *
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
G = [[] for i in range(n + 1)]
for i in range(m):
	(u, v, w) = map(int, input().split())
	G[u].append((v, 2 * w))
	G[v].append((u, 2 * w))
unused = []
dist = [None] + list(map(int, input().split()))
for i in range(1, n + 1):
	unused.append((dist[i], i))
heapify(unused)
while unused:
	(t, nex) = heappop(unused)
	if t > dist[nex]:
		continue
	for edge in G[nex]:
		to = edge[0]
		wt = edge[1]
		if dist[nex] + wt < dist[to]:
			dist[to] = dist[nex] + wt
			heappush(unused, (dist[to], to))
print(*dist[1:])


from __future__ import division, print_function
import os
import sys
import io

class FastI:
	stream = io.BytesIO()
	newlines = 0

	def read1(self):
		(b, ptr) = (os.read(0, (1 << 13) + os.fstat(0).st_size), self.stream.tell())
		self.stream.seek(0, 2)
		self.stream.write(b)
		self.stream.seek(ptr)
		return b

	def read(self):
		while self.read1():
			pass
		return self.stream.read() if self.stream.tell() else self.stream.getvalue()

	def readline(self):
		while self.newlines == 0:
			b = self.read1()
			self.newlines += b.count(b'\n') + (not b)
		self.newlines -= 1
		return self.stream.readline()

	def readnumber(self, var=int):
		b = self.read()
		(num, sign) = (var(0), 1)
		for char in b:
			if char >= b'0'[0]:
				num = 10 * num + char - 48
			elif char == b'-'[0]:
				sign = -1
			elif char != b'\r'[0]:
				yield (sign * num)
				(num, sign) = (var(0), 1)
		if b and b[-1] >= b'0'[0]:
			yield (sign * num)
sys.stdin = FastI()
input = sys.stdin.readline
(sys.stdout, stream) = (io.IOBase(), io.BytesIO())
sys.stdout.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
sys.stdout.write = lambda s: stream.write(s.encode())
sys.stdin = FastI()
input = sys.stdin.readline
big = 3000000000000.0

class segheap:

	def __init__(self, data):
		n = len(data)
		m = 1
		while m < n:
			m *= 2
		self.n = n
		self.m = m
		self.data = [big] * (2 * m)
		for i in range(n):
			self.data[i + m] = data[i]
		for i in reversed(range(m)):
			self.data[i] = min(self.data[2 * i], self.data[2 * i + 1])

	def mini(self):
		i = 1
		while i < self.m:
			if self.data[i] == self.data[2 * i]:
				i = 2 * i
			else:
				i = 2 * i + 1
		i -= self.m
		self.setter(i, big)
		return i

	def setter(self, ind, val):
		ind += self.m
		if val < self.data[ind]:
			while ind > 0 and self.data[ind] > val:
				self.data[ind] = val
				ind //= 2
		elif val > self.data[ind]:
			old_val = self.data[ind]
			self.data[ind] = val
			ind //= 2
			while ind > 0 and self.data[ind] == old_val:
				self.data[ind] = min(self.data[2 * ind], self.data[2 * ind + 1])
				ind //= 2
inp = sys.stdin.readnumber(float)
(n, m) = (int(next(inp)), int(next(inp)))
coupl = [[] for _ in range(n)]
cost = [[] for _ in range(n)]
for _ in range(m):
	v = int(next(inp) - 1)
	u = int(next(inp) - 1)
	w = next(inp)
	coupl[v].append(u)
	coupl[u].append(v)
	cost[u].append(w)
	cost[v].append(w)
best = [next(inp) for i in range(n)]
Q = segheap(best)
while Q.data[1] != big:
	c = Q.data[1]
	node = Q.mini()
	if best[node] != c:
		continue
	for j in range(len(coupl[node])):
		nei = coupl[node][j]
		C = c + 2 * cost[node][j]
		if C < best[nei]:
			best[nei] = C
			Q.setter(nei, C)
for x in best:
	sys.stdout.write(str(int(x)))
	sys.stdout.write(' ')


from __future__ import division, print_function
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import BytesIO, IOBase

class FastI(object):

	def __init__(self, fd=0, buffersize=2 ** 14):
		self.stream = stream = BytesIO()
		self.bufendl = 0

		def read2buffer():
			curpos = stream.tell()
			s = os.read(fd, buffersize + os.fstat(fd).st_size)
			stream.seek(0, 2)
			stream.write(s)
			stream.seek(curpos)
			return s
		self.read2buffer = read2buffer

	def read(self):
		while self.read2buffer():
			pass
		return self.stream.read() if self.stream.tell() else self.stream.getvalue()

	def readline(self):
		while self.bufendl == 0:
			s = self.read2buffer()
			self.bufendl += s.count(b'\n') + (not s)
		self.bufendl -= 1
		return self.stream.readline()

	def input(self):
		return self.readline().rstrip(b'\r\n')

class FastO(IOBase):

	def __init__(self, fd=1):
		stream = BytesIO()
		self.flush = lambda : os.write(1, stream.getvalue()) and (not stream.truncate(0)) and stream.seek(0)
		self.write = stream.write if py2 else lambda s: stream.write(s.encode())
(sys.stdin, sys.stdout) = (FastI(), FastO())
input = sys.stdin.readline
s = sys.stdin.read().replace(b'\r', b'')
inp = []
numb = 0
for i in range(len(s)):
	if s[i] >= 48:
		numb = 10 * numb + s[i] - 48
	elif s[i] != 13:
		inp.append(numb)
		numb = 0
if s[-1] >= 48:
	inp.append(numb)
ind = 0
n = inp[ind]
ind += 1
m = inp[ind]
ind += 1
coupl = [[] for _ in range(n)]
cost = [[] for _ in range(n)]
for _ in range(m):
	v = inp[ind + 0] - 1
	u = inp[ind + 1] - 1
	w = 1.0 * inp[ind + 2]
	ind += 3
	coupl[v].append(u)
	coupl[u].append(v)
	cost[u].append(w)
	cost[v].append(w)
best = [1.0 * inp[ind + i] for i in range(n)]
import heapq
Q = [(best[i], i) for i in range(n)]
heapq.heapify(Q)
while Q:
	(c, node) = heapq.heappop(Q)
	if best[node] != c:
		continue
	for j in range(len(coupl[node])):
		nei = coupl[node][j]
		C = c + 2 * cost[node][j]
		if C < best[nei]:
			best[nei] = C
			heapq.heappush(Q, (C, nei))
for x in best:
	sys.stdout.write(str(int(x)))
	sys.stdout.write(' ')


from heapq import heappush, heappop, heapify
import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
g = [[] for i in range(n + 1)]
for _ in range(m):
	(u, v, w) = map(int, input().split())
	g[u].append((v, w * 2))
	g[v].append((u, w * 2))
a = [''] + list(map(int, input().split()))
ans = a.copy()
hp = [(a[i], i) for i in range(1, n + 1)]
heapify(hp)
while hp:
	(dcur, cur) = heappop(hp)
	if dcur > ans[cur]:
		continue
	for (v, w) in g[cur]:
		if dcur + w < ans[v]:
			ans[v] = dcur + w
			heappush(hp, (ans[v], v))
print(*ans[1:])


from sys import stdin, stdout
from heapq import heapify, heappop, heappush, heappushpop
(n, m) = map(int, stdin.readline().split())
ady = [[] for i in range(n)]
for i in range(m):
	(u, v, w) = map(int, stdin.readline().split())
	ady[u - 1].append((v - 1, 2 * w))
	ady[v - 1].append((u - 1, 2 * w))
c_xcity = list(map(int, stdin.readline().split()))
pq = [(c_xcity[i], i) for i in range(n)]
heapify(pq)
while len(pq) > 0:
	(wu, u) = heappop(pq)
	if c_xcity[u] != wu:
		continue
	for (v, w) in ady[u]:
		if c_xcity[v] > c_xcity[u] + w:
			c_xcity[v] = c_xcity[u] + w
			heappush(pq, (c_xcity[v], v))
stdout.write(' '.join(map(str, c_xcity)))