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 JAVA):

Solution:

import java.io.*;
import java.util.*;

public class D {
	static class pair implements Comparable<pair> {

		int f;
		int s;

		public pair() {

		}

		public pair(int a, int b) {
			f = a;
			s = b;

		}

		@Override
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
			return o.s - this.s;
		}

	}

	static int mod = (int) 1e9 + 7;
	static int ar[];
//	static Scanner sc = new Scanner(System.in);
	static StringBuilder cout = new StringBuilder();
	static ArrayList<Integer> gr[];

	static void buildGraph(int n, int m) throws IOException {

		gr = new ArrayList[n];

		for (int i = 0; i < n; i++) {

			gr[i] = new ArrayList<>();

		}

		for (int i = 0; i < m; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();

			u--;
			v--;
			gr[u].add(v);
			gr[v].add(u);
		}

	}

	static void sort(int a[], int n) {

		ArrayList<Integer> al = new ArrayList<>();

		for (int i = 0; i < n; i++) {

			al.add(a[i]);
		}

		Collections.sort(al);

		for (int i = 0; i < n; i++) {

			a[i] = al.get(i);
		}
	}

	static void in(int a[], int n) throws IOException {
		for (int i = 0; i < n; i++)
			a[i] = sc.nextInt();
	}

	static class pair1 implements Comparable<pair1> {

		int v;
		long wt;
		int f1;
		int f2;

		public pair1() {

		}

		public pair1(int a, long b, int c, int d) {
			v = a;
			wt = b;
			f1 = c;
			f2 = d;

		}

		@Override
		public int compareTo(pair1 o) {
			// TODO Auto-generated method stub
			if (this.wt >= o.wt)
				return 1;
			else 
				return -1;
			
		}

	}

	public static void main(String[] args) throws IOException {
		int t = 1;// sc.nextInt();

		while (t-- > 0) {

			int n=sc.nextInt();
			
			int m=sc.nextInt();
			
			ArrayList<pair>[]gr=new ArrayList[n];
			
			for(int i=0;i<n;i++)
			{
				gr[i]=new  ArrayList<>();
			}
			
			
			for(int i=0;i<m;i++) {
				
				int u=sc.nextInt();
				int v=sc.nextInt();
				int w=sc.nextInt();
				u--;
				v--;
				
				gr[u].add(new pair(v,w));
				gr[v].add(new pair(u,w));
			}
			
			
			PriorityQueue<pair1>pq=new PriorityQueue<>();
			
			
			
			boolean visit[][][]=new boolean[n][2][2];
			long dp[][][]=new long[n][2][2];
			
			for(int i=0;i<n;i++) {
				
				for(int j=0;j<2;j++) {
					
					for(int k=0;k<2;k++) {
						
						dp[i][j][k]=(long)1e18;
					}
				}
			}
			
			pq.add(new pair1(0,0,0,0));
			
			while(!pq.isEmpty()) {
				
				
			
				pair1 p=pq.poll();
				dp[p.v][p.f1][p.f2]=Math.min(dp[p.v][p.f1][p.f2], p.wt);
				if(visit[p.v][p.f1][p.f2])continue;
				visit[p.v][p.f1][p.f2]=true;
				
				
				
				
				
				for(pair nbr:gr[p.v] ) {
					
					if(!visit[nbr.f][p.f1][p.f2]  && dp[nbr.f][p.f1][p.f2]>p.wt+nbr.s)
					
						pq.add(new pair1(nbr.f,p.wt+nbr.s,p.f1,p.f2));
					
					
					if(p.f1==0) {
						
						
						if(!visit[nbr.f][1][p.f2]   && dp[nbr.f][1][p.f2]>p.wt ) {
							
							pq.add(new pair1(nbr.f,p.wt,1,p.f2));
						}
						
						
					}
					
					if(p.f2==0) {
						
						if(!visit[nbr.f][p.f1][1]    && dp[nbr.f][p.f1][1]>p.wt+2*nbr.s ) {
							pq.add(new pair1(nbr.f,p.wt+2*nbr.s,p.f1,1));
						}
						
						
					}
					
					if(p.f1==0 && p.f2==0) {
						
						if(!visit[nbr.f][1][1]   && dp[nbr.f][1][1]>p.wt+nbr.s) {
							pq.add(new pair1(nbr.f,p.wt+nbr.s,1,1));
						}
						
						
					}
					
					
					
				}
				
				
				
			}
			
			
			for(int i=1;i<n;i++) {
				
				cout.append(dp[i][1][1]+" ");
			}
			
			cout.append("\n");
			
			
			
		}
 
		System.out.println(cout);
	}

	
	
	
	static Reader sc=new Reader();
	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}
	
	
	
	
	
}