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();
				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) {

						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 && !visit[nbr.f][1][p.f2]) {

						if ( dp[nbr.f][1][p.f2] > p.wt) {

							dp[nbr.f][1][p.f2]=p.wt;
							pq.add(new pair1(nbr.f, p.wt, 1, p.f2));
						}

					}

					if (p.f2 == 0 && !visit[nbr.f][p.f1][1]) {

						if (  dp[nbr.f][p.f1][1] > p.wt + 2 * nbr.s) {
							
							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) {
							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();
		}
	}
	
	
	
	
	
}