AtCoder. 013 Passing(5)

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

public class Main{
  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  static StringTokenizer st;
  static ArrayList<HashMap<Integer, Integer>> al;
  static int n, m;
  static PriorityQueue<Node> q = new PriorityQueue<>();
  public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    readLine();
    n = getInt();
    m = getInt();
    al = new ArrayList<>();
    for(int i = 0; i <= n; i++) {
      al.add(new HashMap<>());
    }
    for(int i = 0; i < m; i++) {
      readLine();
      int t1 = getInt(), t2 = getInt(), cost = getInt();
      al.get(t1).put(t2, cost);
      al.get(t2).put(t1, cost);
    }
    long[] dp1 = dijkstra(1);
    long[] dpN = dijkstra(n);

    for(int i = 1; i <= n; i++) sb.append(dp1[i] + dpN[i] + "\n");
    System.out.print(sb);
  }

  static long[] dijkstra(int idx) {
    boolean[] visited = new boolean[n + 1];
    long[] dp = new long[n + 1];
    Arrays.fill(dp, Long.MAX_VALUE);
    dp[idx] = 0;
    q.add(new Node(idx, 0));
    while(!q.isEmpty()) {
      Node node = q.poll();
      visited[node.vertex] = true;
      if(dp[node.vertex] < node.cost) continue;
      for(Map.Entry<Integer, Integer> entry : al.get(node.vertex).entrySet()) {
        int desV = entry.getKey(), cost = entry.getValue();
        if(visited[desV]) continue;
        if(dp[desV] > (long)node.cost + cost) {
          dp[desV] = node.cost + cost;
          q.add(new Node(desV, dp[desV]));
        }
      }
    }
    return dp;
  }

  static int getInt() { return Integer.parseInt(st.nextToken()); }
  static void readLine() throws IOException { st = new StringTokenizer(br.readLine()); }
}

class Node implements Comparable<Node> {
  int vertex;
  long cost;

  public Node(int v, long c) { this.vertex = v; this.cost = c; }
  public int compareTo(Node node) { return Long.compare(cost, node.cost); }
}