Problem: 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 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using pi = pair<int, int>;
using ll = long long;
using pl = pair<ll, ll>;
const int nax = 2e5+5;
const int pax = 105;
const double eps = 1e-6;
const ll INF = 1e13;
const int MOD = 1e9+7;

//vector<int> fact(pax), ifact(pax);

int add(int a, int b) {
	int ret = a + b;
	if (ret >= MOD) {
		ret -= MOD;
	}
	return ret;
}

int sub(int a, int b) {
	int ret = a - b;
	if (ret < 0) ret += MOD;
	return ret;
}

int mul(int a, int b) {
	return (1LL * a * b) % MOD;
}

int pow(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1) {
			ans = mul(ans, a);
		}
		a = mul(a, a);
		b >>= 1;
	}
	return ans;
}

int inv(int x) {
	return pow(x, MOD - 2);
}
/*
void init() {
	fact[0] = fact[1] = ifact[0] = ifact[1] = 1;
	for (int i = 2; i < pax; i++) {
		fact[i] = mul(fact[i - 1], i);
	}
	ifact[pax - 1] = inv(fact[pax - 1]);
	for (int i = pax - 2; i >= 2; i--) {
		ifact[i] = mul(i + 1, ifact[i + 1]);
	}
}

int nck(int n, int k) {
	return mul(fact[n], mul(ifact[n - k], ifact[k]));
}

struct block {
	int w;
	int s;
	int v;
};

vector<vector<pi>> intervals(nax);

struct S {
	ll small;
	ll lazy;
	void merge(const S& a, const S& b) {
		small = min(a.small, b.small);
		assert(!lazy);
	}
	void add(ll x) {
		small += x;
		lazy += x;
	}
};

enum class Type {
	Add = 1,
	Min = 2
};

vector<S> tree;

void rec(int id, int l, int r, int ql, int qr, Type t, ll& x) {
	if (l > qr || ql > r) {
		return;
	}
	if (ql <= l && r <= qr) {
		if (t == Type::Add) {
			tree[id].add(x);
		}
		else if (t == Type::Min) {
			x = min(x, tree[id].small);
		}
		else {
			assert(0);
		}
		return;
	}
	for (auto b : { 2 * id, 2 * id + 1 }) {
		tree[b].add(tree[id].lazy);
	}
	tree[id].lazy = 0;
	int mid = (l + r) / 2;
	rec(2 * id, l, mid, ql, qr, t, x);
	rec(2 * id + 1, mid + 1, r, ql, qr, t, x);
	tree[id].merge(tree[2 * id], tree[2 * id + 1]);
}

using vi = vector<int>;
using vvi = vector<vi>;

vvi mul(vvi& a, vvi& b) {
	int n = a.size();
	vvi ret(n, vi(n, 0));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				ret[i][j] = add(ret[i][j], mul(a[i][k], b[k][j]));
			}
		}
	}
	return ret;
}

vvi pow(vvi &a, ll b) {
	int n = a.size();
	vvi ans(n, vi(n, 0));
	for (int i = 0; i < n; i++) {
		ans[i][i] = 1;
	}
	while (b) {
		if (b & 1) {
			ans = mul(ans, a);
		}
		a = mul(a, a);
		b >>= 1;
	}
	return ans;
}

vector<pi> flowers(nax);
vector<ll> st(2 * nax);

ll query(int l, int r, int n) {
	ll ans = 0;
	l += n;
	r += n;
	while (l < r) {
		if (l & 1) ans = max(ans, st[l++]);
		if (r & 1) ans = max(ans, st[--r]);
		l >>= 1;
		r >>= 1;
	}
	return ans;
}

void update(int p, ll val, int n) {
	for (st[p += n] = val; p; p >>= 1) {
		st[p >> 1] = max(st[p], st[p ^ 1]);
	}
}*/

using pli = pair<ll, pair<int, int>>;
vector<vector<pi>> adj(nax);
vector<vector<ll>> dist(nax, vector<ll>(4, INF));
int n;

void dijkstra(int s) {
	dist[s] = { 0, INF, INF, INF };
	priority_queue<pli, vector<pli>, greater<pli>> pq;
	pq.push({ dist[s][0], {0, s} });
	while (!pq.empty()) {
		auto tp = pq.top();
		pq.pop();
		int v = tp.second.second;
		int flag = tp.second.first; // is_taken_free, is_taken_twice
		if (dist[v][flag] < tp.first) continue;
		for (auto edge : adj[v]) {
			int to = edge.first;
			ll len = edge.second;
			switch (flag) {
				case 0:
				{
					for (int nflag : {0, 1, 2, 3}) {
						if (!nflag || nflag == 3) {
							if (dist[v][flag] + len < dist[to][nflag]) {
								dist[to][nflag] = dist[v][flag] + len;
								pq.push({ dist[to][nflag] , {nflag, to} });
							}
						}
						else if (nflag == 1) {
							if (dist[v][flag] < dist[to][nflag]) {
								dist[to][nflag] = dist[v][flag];
								pq.push({ dist[to][nflag] , {nflag, to} });
							}
						}
						else {
							if (dist[v][flag] + 2 * len < dist[to][nflag]) {
								dist[to][nflag] = dist[v][flag] + 2 * len;
								pq.push({ dist[to][nflag] , {nflag, to} });
							}
						}
					}
					break;
				}
				case 1:
				{
					for (int nflag : {1, 3}) {
						if (nflag == 1) {
							if (dist[v][flag] + len < dist[to][nflag]) {
								dist[to][nflag] = dist[v][flag] + len;
								pq.push({ dist[to][nflag] , {nflag, to} });
							}
						}
						else {
							if (dist[v][flag] + 2 * len < dist[to][nflag]) {
								dist[to][nflag] = dist[v][flag] + 2 * len;
								pq.push({ dist[to][nflag] , {nflag, to} });
							}
						}
					}
					break;
				}
				case 2:
				{
					for (int nflag : {2, 3}) {
						if (nflag == 2) {
							if (dist[v][flag] + len < dist[to][nflag]) {
								dist[to][nflag] = dist[v][flag] + len;
								pq.push({ dist[to][nflag] , {nflag, to} });
							}
						}
						else {
							if (dist[v][flag] < dist[to][nflag]) {
								dist[to][nflag] = dist[v][flag];
								pq.push({ dist[to][nflag] , {nflag, to} });
							}
						}
					}
					break;
				}
				case 3:
				{
					for (int nflag : {3}) {
						if (nflag == 3) {
							if (dist[v][flag] + len < dist[to][nflag]) {
								dist[to][nflag] = dist[v][flag] + len;
								pq.push({ dist[to][nflag] , {nflag, to} });
							}
						}
					}
					break;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int m, x, y, w;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> w;
		adj[x].push_back({ y, w });
		adj[y].push_back({ x, w });
	}
	vector<vector<ll>> d;
	dijkstra(1);
	for (int i = 2; i <= n; i++) {
		cout << dist[i][3] << ' ';
	}
	cout << '\n';
	return 0;
}