[백준] 1916번 (java 자바)

import java.util.*;


class Node {
    int end, weight;
    
    public Node(int end, int weight){
        this.end = end;
        this.weight = weight;
    }
}

public class Main
{
    static final int INF = 987654321;
    static List<Node>[] Graph;
    static int[] Dist;
    static int N, M;
    
    
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        Graph = new ArrayList[N + 1];
        Dist = new int[N + 1];
        for(int i = 1; i < N + 1; i++){
            Graph[i] = new ArrayList<>();
        }
        for(int i = 0; i < M; i++){
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            Graph[u].add(new Node(v, w));
        }
        int s = sc.nextInt();
        int e = sc.nextInt();
        dijkstra(s);
        
        System.out.println(Dist[e]);

	}
	
	private static void dijkstra(int src){
	    PriorityQueue<Node> pq = new PriorityQueue<>((a, b)->a.weight - b.weight);
	    boolean[] visited = new boolean[N + 1];
	    for(int i = 1; i < N + 1; i++) Dist[i] = INF;
	    
	    pq.add(new Node(src, 0));
	    Dist[src] = 0;
	    while(!pq.isEmpty()){
	        Node curr = pq.poll();
	        int v = curr.end;
	        if(visited[v]) continue;
	        
	        visited[v] = true;
	        for(Node node : Graph[v]){
	            if(Dist[node.end] > Dist[v] + node.weight){
	                Dist[node.end] = Dist[v] + node.weight;
	                pq.add(new Node(node.end, Dist[node.end]));
	            }
	        }
	        
	        
	    }
	    
	    
	    
	}
}