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.util.*;
import java.io.*;
public class EdA {
	static long[] mods = {1000000007, 998244353, 1000000009};
	static long mod = mods[0];
	public static MyScanner sc;
    public static PrintWriter out;
    static ArrayList<ArrayList<Edge>> graph;
	public static void main(String[] omkar) throws Exception{
		// TODO Auto-generated method stub
 		sc = new MyScanner();
 		out = new PrintWriter(System.out);
//	 		String input1 = bf.readLine().trim();
//	 		String input2 = bf.readLine().trim();
//			COMPARING INTEGER OBJECTS U DO DOT EQUALS NOT ==
 			int n = sc.nextInt();
 			int m = sc.nextInt();
 			graph = new ArrayList<ArrayList<Edge>>();
 			for(int j =0;j<=n;j++){
 				graph.add(new ArrayList<Edge>());
 			}
 			for(int j=0;j<m;j++){
 				int v1 = sc.nextInt();
 				int v2 = sc.nextInt();
 				int w = sc.nextInt();
 				graph.get(v1).add(new Edge(v2, w));
 				graph.get(v2).add(new Edge(v1, w));
 			}
 			//first one is have we subtracted an edge or not, second one is have we added an edge twice or not
 			long[][][] mindist = new long[n+1][2][2];
 			boolean[][][] seen = new boolean[n+1][2][2];
 			for(int j = 0;j<=n;j++){
 				for(int k=0;k<2;k++){
 					Arrays.fill(mindist[j][k],  Long.MAX_VALUE);
 				}
 			}
 			mindist[1][0][0] = 0;
 			PriorityQueue<Vertex> pq = new PriorityQueue<>();
 			pq.add(new Vertex(1, 0, 0, 0));
 			while(!pq.isEmpty()){
 				Vertex v = pq.remove();
 				while(!pq.isEmpty() && seen[v.v][v.first][v.second])
 					v = pq.remove();
 				long currdist = mindist[v.v][v.first][v.second];
 				for(Edge e : graph.get(v.v)){
 					for(int i=0;i<2;i++){
 						for(int j=0;j<2;j++){
 							if (i<v.first || j<v.second || seen[e.v][i][j])
 								continue;
 							long sum = e.w;
 							if (j> v.second && i > v.first)
 								sum+=0;
 							else if(j>v.second)
 								sum+=(long)(e.w);
 							else if (i>v.first)
 								sum-=(long)(e.w);
 							if (currdist+sum < mindist[e.v][i][j]){
 								mindist[e.v][i][j] = currdist+sum;
 								pq.add(new Vertex(e.v, i, j, mindist[e.v][i][j]));
 							}
 								
 						}
 					}
 				}
 				seen[v.v][v.first][v.second] = true;
 			}
 			for(int j=2;j<=n;j++){
 				out.print(mindist[j][1][1] + " ");
 			}
 			out.println();

//	 		for(int j = 0;j<array.length;j++){
//	 			out.print(array[j] + " ");
//	 		}
//	 		out.println();
 
 		out.close();
 	}
	static class Vertex implements Comparable<Vertex>{
		private int v;
		private int first;
		private int second;
		private long distance;
		public Vertex(int v, int first, int second, long distance){
			this.v = v;
			this.first = first;
			this.second = second;
			this.distance = distance;
		}
		public int compareTo(Vertex other){
			return Long.compare(distance,  other.distance);
		}
		
	}
	static class Edge{
		private int v;
		private int w;
		public Edge(int v, int w){
			this.v = v;
			this.w = w;
		}
	}
	public static void sort(int[] array){
		ArrayList<Integer> copy = new ArrayList<>();
		for (int i : array)
			copy.add(i);
		Collections.sort(copy);
		for(int i = 0;i<array.length;i++)
			array[i] = copy.get(i);
	}
	static String[] readArrayString(int n){
		String[] array = new String[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.next();
		return array;
	}
	static int[] readArrayInt(int n){
    	int[] array = new int[n];
    	for(int j = 0;j<n;j++)
    		array[j] = sc.nextInt();
    	return array;
    }
	static int[] readArrayInt1(int n){
		int[] array = new int[n+1];
		for(int j = 1;j<=n;j++){
			array[j] = sc.nextInt();
		}
		return array;
	}
	static long[] readArrayLong(int n){
		long[] array = new long[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextLong();
		return array;
	}
	static double[] readArrayDouble(int n){
		double[] array = new double[n];
		for(int j =0 ;j<n;j++)
			array[j] = sc.nextDouble();
		return array;
	}
	static int minIndex(int[] array){
		int minValue = Integer.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(long[] array){
		long minValue = Long.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static int minIndex(double[] array){
		double minValue = Double.MAX_VALUE;
		int minIndex = -1;
		for(int j = 0;j<array.length;j++){
			if (array[j] < minValue){
				minValue = array[j];
				minIndex = j;
			}
		}
		return minIndex;
	}
	static long power(long x, long y){
		if (y == 0)
			return 1;
		if (y%2 == 1)
			return (x*power(x, y-1))%mod;
		return power((x*x)%mod, y/2)%mod;
	}
	static void verdict(boolean a){
        out.println(a ? "YES" : "NO");
    }
    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;
        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } 
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String nextLine() {
            String str = "";
            try{
                str = br.readLine();
            } 
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        
    }	
}

//StringJoiner sj = new StringJoiner(" "); 
//sj.add(strings)
//sj.toString() gives string of those stuff w spaces or whatever that sequence is