You are given a weighted undirected connected graph consisting of n vertices and m edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Let's define the weight of the path consisting of k edges with indices e_1, e_2, ..., e_k as ∑_{i=1}^{k}{w_{e_i}} - max_{i=1}^{k}{w_{e_i}} + min_{i=1}^{k}{w_{e_i}}, where w_i — weight of the i-th edge in the graph.

Your task is to find the minimum weight of the path from the 1-st vertex to the i-th vertex for each i (2 ≤ i ≤ n).

Input

The first line contains two integers n and m (2 ≤ n ≤ 2 ⋅ 10^5; 1 ≤ m ≤ 2 ⋅ 10^5) — the number of vertices and the number of edges in the graph.

Following m lines contains three integers v_i, u_i, w_i (1 ≤ v_i, u_i ≤ n; 1 ≤ w_i ≤ 10^9; v_i ≠ u_i) — endpoints of the i-th edge and its weight respectively.

Output

Print n-1 integers — the minimum weight of the path from 1-st vertex to the i-th vertex for each i (2 ≤ i ≤ n).

Examples

Input


5 4
5 3 4
2 1 1
3 2 2
2 4 2


Output


1 2 2 4 


Input


6 8
3 1 1
3 6 2
5 4 2
4 2 2
6 1 1
5 2 1
3 2 3
1 5 4


Output


2 1 4 3 1 


Input


7 10
7 5 5
2 3 3
4 7 1
5 3 6
2 7 6
6 2 6
3 7 6
4 2 1
3 1 4
1 7 4


Output


3 4 2 7 7 3

Difficulty: VERY_HARD
Tags: Graph algorithms

Shortest paths

Starter code:

Solutions:
import io
import os

def dijkstra(*args):
	return dijkstraHeapComparatorWrong(*args)

def dijkstraHeap(source, N, getAdj):
	from heapq import heappop, heappush
	inf = float('inf')
	dist = [inf] * N
	dist[source] = 0.0
	queue = [(0.0, float(source))]
	while queue:
		(d, u) = heappop(queue)
		u = int(u)
		if dist[u] == d:
			for (v, w) in getAdj(u):
				cost = d + w
				if cost < dist[v]:
					dist[v] = cost
					heappush(queue, (cost, float(v)))
	return dist

def dijkstraHeapComparatorWrong(source, N, getAdj):
	inf = float('inf')
	dist = [inf] * N
	dist[source] = 0.0
	inQueue = [0] * N
	inQueue[source] = 1
	queue = [source]

	def cmp_lt(u, v):
		return dist[u] < dist[v]
	(heappush, heappop, _) = import_heapq(cmp_lt)
	while queue:
		u = heappop(queue)
		d = dist[u]
		inQueue[u] = 0
		for (v, w) in getAdj(u):
			cost = d + w
			if cost < dist[v]:
				dist[v] = cost
				if not inQueue[v]:
					heappush(queue, v)
					inQueue[v] = 1
	return dist

def dijkstraHeapComparator(source, N, getAdj):
	inf = float('inf')
	dist = [inf] * N
	dist[source] = 0.0

	def cmp_lt(u, v):
		return dist[u] < dist[v]
	(heappush, heappop, _siftdown) = import_heapq(cmp_lt)

	class ListWrapper:

		def __init__(self, maxN):
			self.arr = []
			self.loc = [-1] * maxN

		def append(self, x):
			arr = self.arr
			arr.append(x)
			self.loc[x] = len(arr) - 1

		def pop(self):
			ret = self.arr.pop()
			self.loc[ret] = -1
			return ret

		def index(self, x):
			return self.loc[x]

		def __setitem__(self, i, x):
			self.arr[i] = x
			self.loc[x] = i

		def __getitem__(self, i):
			return self.arr[i]

		def __len__(self):
			return len(self.arr)
	queue = ListWrapper(N)
	queue.append(source)
	while queue:
		u = heappop(queue)
		d = dist[u]
		for (v, w) in getAdj(u):
			cost = d + w
			if cost < dist[v]:
				dist[v] = cost
				heapIndex = queue.index(v)
				if heapIndex == -1:
					heappush(queue, v)
				else:
					_siftdown(queue, 0, heapIndex)
	return dist

def dijkstraSegTree(start, n, getAdj):
	if False:
		inf = -1

		def _min(a, b):
			return a if b == inf or inf != a < b else b
	else:
		inf = float('inf')
		_min = min

	class DistanceKeeper:

		def __init__(self, n):
			m = 1
			while m < n:
				m *= 2
			self.m = m
			self.data = 2 * m * [inf]
			self.dist = n * [inf]

		def __getitem__(self, x):
			return self.dist[x]

		def __setitem__(self, ind, x):
			data = self.data
			self.dist[ind] = x
			ind += self.m
			data[ind] = x
			ind >>= 1
			while ind:
				data[ind] = _min(data[2 * ind], data[2 * ind + 1])
				ind >>= 1

		def trav(self):
			m = self.m
			data = self.data
			dist = self.dist
			while data[1] != inf:
				x = data[1]
				ind = 1
				while ind < m:
					ind = 2 * ind + (data[2 * ind] != x)
				ind -= m
				self[ind] = inf
				dist[ind] = x
				yield ind
	D = DistanceKeeper(n)
	D[start] = 0.0
	for node in D.trav():
		for (nei, weight) in getAdj(node):
			new_dist = D[node] + weight
			if D[nei] == inf or new_dist < D[nei]:
				D[nei] = new_dist
	return D.dist

def dijkstraSortedList(source, N, getAdj):

	class SortedList:

		def __init__(self, iterable=[], _load=200):
			values = sorted(iterable)
			self._len = _len = len(values)
			self._load = _load
			self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
			self._list_lens = [len(_list) for _list in _lists]
			self._mins = [_list[0] for _list in _lists]
			self._fen_tree = []
			self._rebuild = True

		def _fen_build(self):
			self._fen_tree[:] = self._list_lens
			_fen_tree = self._fen_tree
			for i in range(len(_fen_tree)):
				if i | i + 1 < len(_fen_tree):
					_fen_tree[i | i + 1] += _fen_tree[i]
			self._rebuild = False

		def _fen_update(self, index, value):
			if not self._rebuild:
				_fen_tree = self._fen_tree
				while index < len(_fen_tree):
					_fen_tree[index] += value
					index |= index + 1

		def _fen_query(self, end):
			if self._rebuild:
				self._fen_build()
			_fen_tree = self._fen_tree
			x = 0
			while end:
				x += _fen_tree[end - 1]
				end &= end - 1
			return x

		def _fen_findkth(self, k):
			_list_lens = self._list_lens
			if k < _list_lens[0]:
				return (0, k)
			if k >= self._len - _list_lens[-1]:
				return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
			if self._rebuild:
				self._fen_build()
			_fen_tree = self._fen_tree
			idx = -1
			for d in reversed(range(len(_fen_tree).bit_length())):
				right_idx = idx + (1 << d)
				if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
					idx = right_idx
					k -= _fen_tree[idx]
			return (idx + 1, k)

		def _delete(self, pos, idx):
			_lists = self._lists
			_mins = self._mins
			_list_lens = self._list_lens
			self._len -= 1
			self._fen_update(pos, -1)
			del _lists[pos][idx]
			_list_lens[pos] -= 1
			if _list_lens[pos]:
				_mins[pos] = _lists[pos][0]
			else:
				del _lists[pos]
				del _list_lens[pos]
				del _mins[pos]
				self._rebuild = True

		def _loc_left(self, value):
			if not self._len:
				return (0, 0)
			_lists = self._lists
			_mins = self._mins
			(lo, pos) = (-1, len(_lists) - 1)
			while lo + 1 < pos:
				mi = lo + pos >> 1
				if value <= _mins[mi]:
					pos = mi
				else:
					lo = mi
			if pos and value <= _lists[pos - 1][-1]:
				pos -= 1
			_list = _lists[pos]
			(lo, idx) = (-1, len(_list))
			while lo + 1 < idx:
				mi = lo + idx >> 1
				if value <= _list[mi]:
					idx = mi
				else:
					lo = mi
			return (pos, idx)

		def _loc_right(self, value):
			if not self._len:
				return (0, 0)
			_lists = self._lists
			_mins = self._mins
			(pos, hi) = (0, len(_lists))
			while pos + 1 < hi:
				mi = pos + hi >> 1
				if value < _mins[mi]:
					hi = mi
				else:
					pos = mi
			_list = _lists[pos]
			(lo, idx) = (-1, len(_list))
			while lo + 1 < idx:
				mi = lo + idx >> 1
				if value < _list[mi]:
					idx = mi
				else:
					lo = mi
			return (pos, idx)

		def add(self, value):
			_load = self._load
			_lists = self._lists
			_mins = self._mins
			_list_lens = self._list_lens
			self._len += 1
			if _lists:
				(pos, idx) = self._loc_right(value)
				self._fen_update(pos, 1)
				_list = _lists[pos]
				_list.insert(idx, value)
				_list_lens[pos] += 1
				_mins[pos] = _list[0]
				if _load + _load < len(_list):
					_lists.insert(pos + 1, _list[_load:])
					_list_lens.insert(pos + 1, len(_list) - _load)
					_mins.insert(pos + 1, _list[_load])
					_list_lens[pos] = _load
					del _list[_load:]
					self._rebuild = True
			else:
				_lists.append([value])
				_mins.append(value)
				_list_lens.append(1)
				self._rebuild = True

		def discard(self, value):
			_lists = self._lists
			if _lists:
				(pos, idx) = self._loc_right(value)
				if idx and _lists[pos][idx - 1] == value:
					self._delete(pos, idx - 1)

		def remove(self, value):
			_len = self._len
			self.discard(value)
			if _len == self._len:
				raise ValueError('{0!r} not in list'.format(value))

		def pop(self, index=-1):
			(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
			value = self._lists[pos][idx]
			self._delete(pos, idx)
			return value

		def bisect_left(self, value):
			(pos, idx) = self._loc_left(value)
			return self._fen_query(pos) + idx

		def bisect_right(self, value):
			(pos, idx) = self._loc_right(value)
			return self._fen_query(pos) + idx

		def count(self, value):
			return self.bisect_right(value) - self.bisect_left(value)

		def __len__(self):
			return self._len

		def __getitem__(self, index):
			(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
			return self._lists[pos][idx]

		def __delitem__(self, index):
			(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
			self._delete(pos, idx)

		def __contains__(self, value):
			_lists = self._lists
			if _lists:
				(pos, idx) = self._loc_left(value)
				return idx < len(_lists[pos]) and _lists[pos][idx] == value
			return False

		def __iter__(self):
			return (value for _list in self._lists for value in _list)

		def __reversed__(self):
			return (value for _list in reversed(self._lists) for value in reversed(_list))

		def __repr__(self):
			return 'SortedList({0})'.format(list(self))
	inf = float('inf')
	dist = [inf] * N
	dist[source] = 0.0
	queue = SortedList([(0.0, float(source))])
	while queue:
		(negD, u) = queue.pop(-1)
		d = -negD
		u = int(u)
		for (v, w) in getAdj(u):
			prevCost = dist[v]
			cost = d + w
			if cost < prevCost:
				if prevCost != inf:
					queue.discard((-prevCost, float(v)))
				dist[v] = cost
				queue.add((-cost, float(v)))
	return dist

def import_heapq(cmp_lt):
	import sys
	if sys.version_info < (3,):
		import heapq
		from heapq import heappush, heappop, _siftdown
		heapq.cmp_lt = cmp_lt
	else:

		def heappush(heap, item):
			heap.append(item)
			_siftdown(heap, 0, len(heap) - 1)

		def heappop(heap):
			lastelt = heap.pop()
			if heap:
				returnitem = heap[0]
				heap[0] = lastelt
				_siftup(heap, 0)
				return returnitem
			return lastelt

		def _siftdown(heap, startpos, pos):
			newitem = heap[pos]
			while pos > startpos:
				parentpos = pos - 1 >> 1
				parent = heap[parentpos]
				if cmp_lt(newitem, parent):
					heap[pos] = parent
					pos = parentpos
					continue
				break
			heap[pos] = newitem

		def _siftup(heap, pos):
			endpos = len(heap)
			startpos = pos
			newitem = heap[pos]
			childpos = 2 * pos + 1
			while childpos < endpos:
				rightpos = childpos + 1
				if rightpos < endpos and (not cmp_lt(heap[childpos], heap[rightpos])):
					childpos = rightpos
				heap[pos] = heap[childpos]
				pos = childpos
				childpos = 2 * pos + 1
			heap[pos] = newitem
			_siftdown(heap, startpos, pos)
	return (heappush, heappop, _siftdown)
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(N, M) = [int(x) for x in input().split()]
graph = [[] for i in range(N)]
for i in range(M):
	(u, v, w) = [int(x) for x in input().split()]
	u -= 1
	v -= 1
	graph[u].append((v, w))
	graph[v].append((u, w))

def getAdj(node):
	u = node >> 2
	state = node & 3
	for (v, w) in graph[u]:
		vBase = v << 2
		yield (vBase | state, w)
		if not state & 1:
			yield (vBase | state | 1, 0)
		if not state & 2:
			yield (vBase | state | 2, 2 * w)
		if not state & 3:
			yield (vBase | state | 3, w)
dist = dijkstra(0, 4 * N, getAdj)
print(' '.join((str(int(dist[u << 2 | 3])) for u in range(1, N))))