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.BufferedOutputStream;
import java.io.Closeable;
import java.io.DataInputStream;
import java.io.Flushable;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
import java.util.Objects;
import java.util.PriorityQueue;

/** Built using CHelper plug-in Actual solution is at the top */
public class Main {
  static class TaskAdapter implements Runnable {
    @Override
    public void run() {
      InputStream inputStream = System.in;
      OutputStream outputStream = System.out;
      FastReader in = new FastReader(inputStream);
      Output out = new Output(outputStream);
      EMinimumPath solver = new EMinimumPath();
      solver.solve(1, in, out);
      out.close();
    }
  }

  public static void main(String[] args) throws Exception {
    Thread thread = new Thread(null, new TaskAdapter(), "", 1 << 26);
    thread.start();
    thread.join();
  }

  static class EMinimumPath {
    public EMinimumPath() {}

    public void solve(int kase, InputReader in, Output pw) {
      int n = in.nextInt(), m = in.nextInt();
      var graph = in.nextUndirectedWeightedGraph(n, m);
      long[][] dist = new long[n][4];
      for (int i = 0; i < n; i++) {
        dist[i][0] = dist[i][1] = dist[i][2] = dist[i][3] = -1;
      }
      PriorityQueue<EMinimumPath.State> pq =
          new PriorityQueue<>((int) 4e7, Comparator.comparingLong(o -> o.dist));
      pq.add(new EMinimumPath.State(0, 0, 0));
      while (!pq.isEmpty()) {
        var cur = pq.poll();
        if (dist[cur.u][cur.x] != -1) {
          continue;
        }
        dist[cur.u][cur.x] = cur.dist;
        for (var v : graph[cur.u]) {
          for (int i = 0; i < 4; i++) {
            if (dist[v.a][cur.x | i] == -1 && (i & cur.x) == 0) {
              if (i == 0 || i == 3) {
                pq.add(new EMinimumPath.State(v.a, cur.x | i, cur.dist + v.b));
              } else if (i == 1) {
                pq.add(new EMinimumPath.State(v.a, cur.x | i, cur.dist + 2L * v.b));
              } else {
                pq.add(new EMinimumPath.State(v.a, cur.x | i, cur.dist));
              }
            }
          }
        }
      }
      for (int i = 1; i < n; i++) {
        pw.print(dist[i][3] + " ");
      }
    }

    static class State {
      int u;
      int x;
      long dist;

      public State(int u, int x, long dist) {
        this.u = u;
        this.x = x;
        this.dist = dist;
      }
    }
  }

  static class Pair<T1, T2> implements Comparable<Pair<T1, T2>> {
    public T1 a;
    public T2 b;

    public Pair(Pair<T1, T2> p) {
      this(p.a, p.b);
    }

    public Pair(T1 a, T2 b) {
      this.a = a;
      this.b = b;
    }

    public String toString() {
      return a + " " + b;
    }

    public int hashCode() {
      return Objects.hash(a, b);
    }

    public boolean equals(Object o) {
      if (o instanceof Pair) {
        Pair p = (Pair) o;
        return a.equals(p.a) && b.equals(p.b);
      }
      return false;
    }

    public int compareTo(Pair<T1, T2> p) {
      int cmp = ((Comparable<T1>) a).compareTo(p.a);
      if (cmp == 0) {
        return ((Comparable<T2>) b).compareTo(p.b);
      }
      return cmp;
    }
  }

  static interface InputReader {
    int nextInt();

    default ArrayList<Pair<Integer, Integer>>[] nextUndirectedWeightedGraph(int n, int m) {
      ArrayList<Pair<Integer, Integer>>[] ret = new ArrayList[n];
      for (int i = 0; i < n; i++) {
        ret[i] = new ArrayList<>();
      }
      for (int i = 0; i < m; i++) {
        int u = nextInt() - 1, v = nextInt() - 1, w = nextInt();
        ret[u].add(new Pair<>(v, w));
        ret[v].add(new Pair<>(u, w));
      }
      return ret;
    }
  }

  static class Output implements Closeable, Flushable {
    public StringBuilder sb;
    public OutputStream os;
    public int BUFFER_SIZE;
    public String lineSeparator;

    public Output(OutputStream os) {
      this(os, 1 << 16);
    }

    public Output(OutputStream os, int bs) {
      BUFFER_SIZE = bs;
      sb = new StringBuilder(BUFFER_SIZE);
      this.os = new BufferedOutputStream(os, 1 << 17);
      lineSeparator = System.lineSeparator();
    }

    public void print(String s) {
      sb.append(s);
      if (sb.length() > BUFFER_SIZE >> 1) {
        flushToBuffer();
      }
    }

    private void flushToBuffer() {
      try {
        os.write(sb.toString().getBytes());
      } catch (IOException e) {
        e.printStackTrace();
      }
      sb = new StringBuilder(BUFFER_SIZE);
    }

    public void flush() {
      try {
        flushToBuffer();
        os.flush();
      } catch (IOException e) {
        e.printStackTrace();
      }
    }

    public void close() {
      flush();
      try {
        os.close();
      } catch (IOException e) {
        e.printStackTrace();
      }
    }
  }

  static class FastReader implements InputReader {
    private final int BUFFER_SIZE = 1 << 16;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer;
    private int bytesRead;

    public FastReader(InputStream is) {
      din = new DataInputStream(is);
      buffer = new byte[BUFFER_SIZE];
      bufferPointer = bytesRead = 0;
    }

    public int nextInt() {
      int ret = 0;
      byte c = skipToDigit();
      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;
    }

    private boolean isDigit(byte b) {
      return b >= '0' && b <= '9';
    }

    private byte skipToDigit() {
      byte ret;
      while (!isDigit(ret = read()) && ret != '-')
        ;
      return ret;
    }

    private void fillBuffer() {
      try {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
      } catch (IOException e) {
        e.printStackTrace();
        throw new InputMismatchException();
      }
      if (bytesRead == -1) {
        buffer[0] = -1;
      }
    }

    private byte read() {
      if (bytesRead == -1) {
        throw new InputMismatchException();
      } else if (bufferPointer == bytesRead) {
        fillBuffer();
      }
      return buffer[bufferPointer++];
    }
  }

  static class Utilities {
    public static class Debug {
      public static boolean LOCAL = System.getProperty("ONLINE_JUDGE") == null;

      private static <T> String ts(T t) {
        if (t == null) {
          return "null";
        }
        try {
          return ts((Iterable) t);
        } catch (ClassCastException e) {
          if (t instanceof int[]) {
            String s = Arrays.toString((int[]) t);
            return "{" + s.substring(1, s.length() - 1) + "}";
          } else if (t instanceof long[]) {
            String s = Arrays.toString((long[]) t);
            return "{" + s.substring(1, s.length() - 1) + "}";
          } else if (t instanceof char[]) {
            String s = Arrays.toString((char[]) t);
            return "{" + s.substring(1, s.length() - 1) + "}";
          } else if (t instanceof double[]) {
            String s = Arrays.toString((double[]) t);
            return "{" + s.substring(1, s.length() - 1) + "}";
          } else if (t instanceof boolean[]) {
            String s = Arrays.toString((boolean[]) t);
            return "{" + s.substring(1, s.length() - 1) + "}";
          }
          try {
            return ts((Object[]) t);
          } catch (ClassCastException e1) {
            return t.toString();
          }
        }
      }

      private static <T> String ts(T[] arr) {
        StringBuilder ret = new StringBuilder();
        ret.append("{");
        boolean first = true;
        for (T t : arr) {
          if (!first) {
            ret.append(", ");
          }
          first = false;
          ret.append(ts(t));
        }
        ret.append("}");
        return ret.toString();
      }

      private static <T> String ts(Iterable<T> iter) {
        StringBuilder ret = new StringBuilder();
        ret.append("{");
        boolean first = true;
        for (T t : iter) {
          if (!first) {
            ret.append(", ");
          }
          first = false;
          ret.append(ts(t));
        }
        ret.append("}");
        return ret.toString();
      }

      public static void dbg(Object... o) {
        if (LOCAL) {
          System.err.print(
              "Line #" + Thread.currentThread().getStackTrace()[2].getLineNumber() + ": [");
          for (int i = 0; i < o.length; i++) {
            if (i != 0) {
              System.err.print(", ");
            }
            System.err.print(ts(o[i]));
          }
          System.err.println("]");
        }
      }
    }
  }
}