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 static java.lang.Math.max;
import static java.lang.Math.min;
import static java.lang.Math.abs;
import java.io.*;
import java.util.*;

public class A
{
    static int n, m;
    static int[] arr;
    static char[] s;
    static List<int[]> adj[];
    public static void main(String[] args) throws IOException
    {
        f = new Flash();
        out = new PrintWriter(System.out);
        
        int T = 1; //ni();
        for(int tc = 1; tc <= T; tc++){
            n = ni(); m = ni();
            adj = new ArrayList[n];
            for(int i = 0; i < n; i++) adj[i] = new ArrayList<>();
            for(int i = 1; i <= m; i++) {
            	int u = ni()-1, v = ni()-1, w = ni();
            	adj[u].add(new int[] {v, w});
            	adj[v].add(new int[] {u, w});
            }
            
            fn();
        }
        
        out.flush(); out.close();
    }
    
    static void fn()
    {
    	/*
    	 * https://codeforces.com/blog/entry/86827?#comment-749632
    	 * 
    	 * dp[u][0] :Minimum Path length from vertex 1 to u such that each edge in path is counted once .

dp[u][1] :Minimum Path length from vertex 1 to u such that one edge in path is counted one more time.

dp[u][2] :Minimum Path length from vertex 1 to u such that one edge in path is subtracted.

dp[u][3] :Minimum Path length from vertex 1 to u such that one edge in path is counted one more time and one edge in path is subtracted 
(Note that both type of edges can be same and in that case it will be equivalent to dp[u][0]).
    	 */
    	
        long[][] dp = new long[n][4];
        for(int i = 0; i < n; i++) Arrays.fill(dp[i], (long)1e18);
        dp[0][0] = 0L;
        boolean[][] vis = new boolean[n][4];
        PriorityQueue<long[]> pq = new PriorityQueue<>(new sort());
        pq.add(new long[] {0, 0, 0});
        while(!pq.isEmpty()) {
        	long[] node = pq.poll();
        	int u = (int)node[0], state = (int)node[1];
        	long dist = node[2];
        	if(vis[u][state]) continue;
        	vis[u][state] = true;
        	
        	for(int[] vw : adj[u]) {
        		int v = vw[0], w = vw[1];
        		if(state == 0) {
        			if(dp[v][0] > dp[u][0] + w) {
        				dp[v][0] = dp[u][0] + w;
        				pq.add(new long[] {v, 0, dp[v][0]});
        			}
        			
        			if(dp[v][1] > dp[u][0] + 2*w) {
        				dp[v][1] = dp[u][0] + 2*w;
        				pq.add(new long[] {v, 1, dp[v][1]});
        			}
        			
        			if(dp[v][2] > dp[u][0]) {
        				dp[v][2] = dp[u][0];
        				pq.add(new long[] {v, 2, dp[v][2]});
        			}
        			
        			if(dp[v][3] > dp[u][0] + w) {
        				dp[v][3] = dp[u][0] + w;
        				pq.add(new long[] {v, 3, dp[v][3]});
        			}
        		}
        		
        		else if(state == 1) {
        			if(dp[v][1] > dp[u][1] + w) {
        				dp[v][1] = dp[u][1] + w;
        				pq.add(new long[] {v, 1, dp[v][1]});
        			}
        			
        			if(dp[v][3] > dp[u][1]) {
        				dp[v][3] = dp[u][1];
        				pq.add(new long[]{v, 3, dp[v][3]});
        			}
        		}
        		
        		else if(state == 2) {
        			if(dp[v][2] > dp[u][2] + w) {
        				dp[v][2] = dp[u][2] + w;
        				pq.add(new long[] {v, 2, dp[v][2]});
        			}
        			
        			if(dp[v][3] > dp[u][2] + 2*w) {
        				dp[v][3] = dp[u][2] + 2*w;
        				pq.add(new long[] {v, 3, dp[v][3]});
        			}
        		}
        		
        		else if(state == 3) {
        			if(dp[v][3] > dp[u][3] + w) {
        				dp[v][3] = dp[u][3] + w;
        				pq.add(new long[] {v, 3, dp[v][3]});
        			}
        		}
        	}
        }
        
        long[] ans = new long[n-1];
        for(int i = 1; i < n; i++) {
        	ans[i-1] = dp[i][3];
        }
        
        print(ans);
    }
    
    static class sort implements Comparator<long[]>{
    	public int compare(long[] a, long[] b) {
    		return Long.compare(a[2], b[2]);
    	}
    }
    
    static Flash f;
    static PrintWriter out;
    static final long mod = (long)1e9+7;
    static final long inf = Long.MAX_VALUE;
    static final int _inf = Integer.MAX_VALUE;
    static final int maxN = (int)5e5+5;
    static long[] fact, inv;
    
    static void sort(int[] a){
        List<Integer> A = new ArrayList<>();
        for(int i : a) A.add(i);
        Collections.sort(A);
        for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
    }
    
    static void sort(long[] a){
        List<Long> A = new ArrayList<>();
        for(long i : a) A.add(i);
        Collections.sort(A);
        for(int i = 0; i < A.size(); i++) a[i] = A.get(i);
    }
    
    static void print(int[] a){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
        sop(sb);
    }
    
    static void print(long[] a){
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < a.length; i++) sb.append(a[i] + " ");
        sop(sb);
    }
    
    static int swap(int itself, int dummy){return itself;}
    static long swap(long itself, long dummy){return itself;}
    static void sop(Object o){out.println(o);}
    static int ni(){return f.ni();}
    static long nl(){return f.nl();}
    static double nd(){return f.nd();}
    static String next(){return f.next();}
    static String ns(){return f.ns();}
    static char[] nc(){return f.nc();}
    static int[] arr(int len){return f.arr(len);}
    static int gcd(int a, int b){if(b == 0) return a; return gcd(b, a%b);}
    static long gcd(long a, long b){if(b == 0) return a; return gcd(b, a%b);}
    static int lcm(int a, int b){return (a*b)/gcd(a, b);}
    static long lcm(long a, long b){return (a*b)/gcd(a, b);}
    
    static class Flash
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        
        String next(){
            while(!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            
            return st.nextToken();
        }
        
        String ns(){
            String s = new String();
            try{
                s = br.readLine().trim();
            }catch(IOException e){
                e.printStackTrace();
            }
            
            return s;
        }
        
        int[] arr(int n){
            int[] a = new int[n];
            for(int i = 0; i < n; i++) a[i] = ni();
            return a;
        }
        
        char[] nc(){return ns().toCharArray();}
        int ni(){return Integer.parseInt(next());}
        long nl(){return Long.parseLong(next());}
        double nd(){return Double.parseDouble(next());}
    }
}