最短路

 
import java.util.*;

public class Main {
    private static List<int[]>[] graph; 

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        graph = new ArrayList[n + 1];//编号从1开始
        Arrays.setAll(graph, k -> new ArrayList<>());
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
            graph[u].add(new int[]{v, w}); 
        }

        int[] dist = spfa(1);
        for(int i=2;i<=n;i++){
            System.out.println(dist[i]);
        }
    }
    
    // 求最短路径
    public static int[] spfa(int start) {
        int[] dist = new int[graph.length];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        boolean[] visited = new boolean[graph.length];
        visited[start] = true;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            int cur = queue.poll();
            visited[cur] = false; // 出队节点的可再次被更新 
            for (int[] edge : graph[cur]) {
                int next = edge[0], weight = edge[1];
                if (dist[next] > dist[cur] + weight) {
                    dist[next] = dist[cur] + weight;
                    if (!visited[next]) {
                        queue.offer(next);
                        visited[next] = true;
                    }
                }
            }
        }
        return dist;
    }
}