【模板】单源最短路2

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);

        // 初始化节点数组（索引从1到5000）
        Point[] points = new Point[5001];
        for (int i = 1; i <= 5000; i++) {
            points[i] = new Point(i);
        }

        // 读取边
        for (int i = 0; i < m; i++) {
            line = br.readLine().split(" ");
            int u = Integer.parseInt(line[0]);
            int v = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);

            // 无向图，添加双向边
            points[u].vectors.put(v, w);
            points[v].vectors.put(u, w);
        }

        // 使用优先队列实现Dijkstra算法
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        pq.offer(new int[] {1, 0}); // [节点, 距离]
        points[1].score = 0; // 起点距离为0

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int node = cur[0];
            int dist = cur[1];

            // 如果当前距离大于记录的距离，表示已经访问了，跳过
            if (dist != points[node].score) continue;


            // 到达终点，输出结果
            if (node == n) {
                bw.write(String.valueOf(dist));
                bw.flush();
                bw.close();
                return;
            }

            // 遍历邻居节点
            for (Map.Entry<Integer, Integer> entry : points[node].vectors.entrySet()) {
                int neighbor = entry.getKey();
                int weight = entry.getValue();
                int newDist = dist + weight;

                if (newDist < points[neighbor].score) {
                    points[neighbor].score = newDist;
                    pq.offer(new int[] {neighbor, newDist});
                }
            }
        }

        // 无法到达终点
        bw.write("-1");
        bw.flush();
        bw.close();
    }

    static class Point {
        int number;
        HashMap<Integer, Integer> vectors; 
        int score; 

        public Point(int number) {
            this.number = number;
            this.vectors = new HashMap<>();
            this.score = Integer.MAX_VALUE;
        }
    }
}