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 <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using std::priority_queue;
const int maxn=2e5+5;
#define int long long
#define rep(a,b,c) for(int a=b;a<=c;a++)
#define repe(x) for(int i=head[x],v;i&&(v=e[i].v);i=e[i].u)
template<class T>inline void read(T &x) {
	T f=1;x=0;char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
	x*=f;
}
struct Edge {
	int u,v,w;
}e[maxn*12];
int head[maxn*3],ecnt;
int n,m,a[maxn],b[maxn],c[maxn],pdis[maxn],dis[maxn*3];
inline void addedge(int u,int v,int w) { e[++ecnt].v=v; e[ecnt].w=w; e[ecnt].u=head[u];head[u]=ecnt; }
inline void add(int u,int v,int w) { addedge(u,v,w); addedge(v,u,w); }
struct node {
    int u,d;
    bool operator <(const node& rhs) const {
        return d>rhs.d;
    }
};
priority_queue<node> Q;
inline void dij() {
	memset(dis,0x3f,sizeof(dis)); dis[1]=0;
	Q.push((node){1,0});
    while (!Q.empty()) {
        node fr=Q.top(); Q.pop();
        int u=fr.u,d=fr.d;
        if(d!=dis[u]) continue;
        repe(u) {
            if (dis[u]+e[i].w<dis[v]) {
                dis[v]=dis[u]+e[i].w;
                Q.push((node){v,dis[v]});
            }
        }
    }
}
signed main() {
	memset(pdis,0x3f,sizeof(pdis));
	read(n); read(m);
	rep(i,1,m) read(a[i]),read(b[i]),read(c[i]),add(a[i],b[i],c[i]);
	rep(i,1,m) {
		add(n+a[i],n+b[i],c[i]);
		add(n*2+a[i],n*2+b[i],c[i]);
		addedge(a[i],n+b[i],c[i]*2);
		addedge(b[i],n+a[i],c[i]*2);
		addedge(n+a[i],n*2+b[i],0);
		addedge(n+b[i],n*2+a[i],0);
		addedge(a[i],n*2+b[i],c[i]);
		addedge(b[i],n*2+a[i],c[i]);
	}
	dij();
	rep(i,2,n) pdis[i]=std::min(pdis[i],dis[i+n*2]);
	memset(e,0,sizeof(e)); memset(head,0,sizeof(head)); ecnt=0;
	rep(i,1,m) {
		add(a[i],b[i],c[i]);
		add(n+a[i],n+b[i],c[i]);
		add(n*2+a[i],n*2+b[i],c[i]);
		addedge(n+a[i],n*2+b[i],c[i]*2);
		addedge(n+b[i],n*2+a[i],c[i]*2);
		addedge(a[i],n+b[i],0);
		addedge(b[i],n+a[i],0);
		addedge(a[i],n*2+b[i],c[i]);
		addedge(b[i],n*2+a[i],c[i]);
	}
	dij();
	rep(i,2,n) printf("%lld ",std::min(pdis[i],dis[i+n*2]));
}