[BOJ] 1753. 최단경로

import java.util.*;

public class Main {
    static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    static int[] d = new int [100001];
    static final int INF = (int) 1e9;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int V = sc.nextInt();
        int E = sc.nextInt();
        int K = sc.nextInt();
        
        for(int i = 0; i <= V; i++){
            graph.add(new ArrayList<Node>());
        }
        
        for(int i = 0; i < E; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph.get(a).add(new Node(b,c));
        }
        
        Arrays.fill(d,INF);
        
        dijkstra(K);
        
        for(int i = 1; i <= V; i++){
            if(d[i]==INF){
                System.out.println("INF");
            } else {
                System.out.println(d[i]);
            }
        }
    }
    
    public static void dijkstra(int K){
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(K,0));
        d[K] = 0;
        while(!pq.isEmpty()){
            Node node = pq.poll();
            int dist = node.getDistance();
            int now = node.getIndex();
            if(d[now] < dist) continue;
            for(int i = 0; i < graph.get(now).size(); i++){
                int cost = d[now] + graph.get(now).get(i).getDistance();
                if(cost < d[graph.get(now).get(i).getIndex()]) {
                    d[graph.get(now).get(i).getIndex()] = cost;
                    pq.add(new Node(graph.get(now).get(i).getIndex(),cost));
                }
            }
        }
    }
}
class Node implements Comparable<Node> {
    int index, distance;
    Node(int index, int distance) {
        this.index = index;
        this.distance = distance;        
    }
    public int getIndex() {
        return this.index;
    }
    public int getDistance() {
        return this.distance;
    }
    @Override
    public int compareTo(Node other) {
        if(this.distance < other.distance) {
            return -1;
        }
        return 1;
    }
}