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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <stack>
#include <sstream>
#include <cstring>
#include <numeric>
#include <ctime>
#include <cassert>
#include <random>
#include <valarray>
//#include <fstream>

#define re return
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)(x).size())
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define y0 y32479
#define y1 y95874
#define next next239
#define prev prev239
#define fill(x, y) memset(x, y, sizeof(x))
#define sqr(x) ((x)*(x))
#define sqrt(x) sqrt(abs(x))
#define unq(x) (x.resize(unique(all(x)) - x.begin()))
#define ba back()
#define popcount __builtin_popcountll
#define fastIO() {ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);}

#ifdef LOCAL_BOBER
bool local = true;
#define deb(x) cout << #x << " = " << (x) << endl
#define debn(x, n) { cout << #x << "(" << n << ") = " << \
	"{"; int _f_ = 1; rep(_i_, n) {if (!_f_) cout << "|"; cout << x[_i_]; _f_= 0;} cout << "}" << endl;}
#define deba(x) { cout << #x << " (size: " << sz(x) << ") = " << \
	"{"; int _f_ = 1; for (auto o : x) {if (!_f_) cout << "|"; cout << o; _f_ = 0;} cout << "}" << endl;}
#else
bool local = false;
#define deb(x) ;
#define debn(x, n) ;
#define deba(x) ;
#define endl "\n"
#endif

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<string> vs;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef pair<double, double> pdd;
typedef long double LD;
typedef double D;

template<class T> void print(T v) { cout << sz(v) << endl; for (auto x : v) cout << x << ' '; cout << endl; };
template<class T> void print1(T v) { cout << sz(v) << endl; for (auto x : v) cout << x + 1 << ' '; cout << endl; };
template<class T1, class T2> ostream& operator << (ostream &o, pair<T1, T2> x) {re o << x.fi << ' ' << x.se;}
template<class T1, class T2> istream& operator >> (istream &o, pair<T1, T2> &x) {re o >> x.fi >> x.se;}
template<class T1, class T2> pair<T1, T2> operator + (pair<T1, T2> a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se; re a;}
template<class T1, class T2> pair<T1, T2> operator - (pair<T1, T2> a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se; re a;}
template<class T1, class T2> void operator += (pair<T1, T2> &a, pair<T1, T2> b) {a.fi += b.fi; a.se += b.se;}
template<class T1, class T2> void operator -= (pair<T1, T2> &a, pair<T1, T2> b) {a.fi -= b.fi; a.se -= b.se;}

int nint() {int x; cin >> x; re x;}
double getTime() { re clock() / (double) CLOCKS_PER_SEC;};

mt19937 rnd(0);
int rand(int n) { re rnd() % n; }
int rand(int l, int r) { re rnd() % (r - l + 1) + l; }

const int mod = 1000000000 + 7;

void initIO() {
	if (local) {
		freopen("input.txt", "r", stdin);
		//freopen("output.txt", "w", stdout);
		srand((int)time(0));
		rnd.seed((int)time(0));
	}
	else {
		//freopen("input.txt", "r", stdin);
		//freopen("output.txt", "w", stdout);
		fastIO();
	}
}

void solve();

signed main() {
	initIO();

	int tc = 1;
//	cin >> tc;
	rep(tt, tc) {
//		cout << "Case #" << tt + 1 << ": ";
		solve();
	}

	if (local)
		cout << endl << "time = " << getTime() << endl;
}


/* ================ actual code starts here ================ */

int n;
int m;

vii v[200500];

long long d[200500][2][2];

using bu = pair<int, ii>;

bool f(bu a, bu b) {
	if (d[a.fi][a.se.fi][a.se.se] != d[b.fi][b.se.fi][b.se.se])
		re d[a.fi][a.se.fi][a.se.se] < d[b.fi][b.se.fi][b.se.se];
	re a < b;
}


void dij(int p, int f1, int f2) {
	fill(d, -1);
	d[p][f1][f2] = 0;
	set<bu, bool (*) (bu, bu)> s(f);
	s.insert(mp(p, mp(f1, f2)));
	while (!s.empty()) {
		bu o = *s.begin();
		s.erase(o);
		int x = o.fi;
		int f1 = o.se.fi;
		int f2 = o.se.se;
		long long dd = d[x][f1][f2];
		for (ii xo : v[x]) {
			int y = xo.fi;
			int dist = xo.se;
			if (d[y][f1][f2] == -1 || d[y][f1][f2] > dd + dist) {
				s.erase(mp(y, mp(f1, f2)));
				d[y][f1][f2] = dd + dist;
				s.insert(mp(y, mp(f1, f2)));
			}
			if (f1 == 0) {
				if (d[y][1][f2] == -1 || d[y][1][f2] > dd + 2 * dist) {
					s.erase(mp(y, mp(1, f2)));
					d[y][1][f2] = dd + 2 * dist;
					s.insert(mp(y, mp(1, f2)));
				}
			}
			if (f2 == 0) {
				if (d[y][f1][1] == -1 || d[y][f1][1] > dd) {
					s.erase(mp(y, mp(f1, 1)));
					d[y][f1][1] = dd;
					s.insert(mp(y, mp(f1, 1)));
				}
			}
			if (f1 == 0 && f2 == 0) {
				if (d[y][1][1] == -1 || d[y][1][1] > dd + dist) {
					s.erase(mp(y, mp(1, 1)));
					d[y][1][1] = dd + dist;
					s.insert(mp(y, mp(1, 1)));
				}
			}
		}
	}
}

void solve() {
	cin >> n >> m;
	rep(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		a--;
		b--;
		v[a].pb(b, c);
		v[b].pb(a, c);
	}

	dij(0, 0, 0);

	for (int i = 1; i < n; i++)
		cout << d[i][1][1] << ' ';
}