所有的知识点，易错点，与其他题目的联系都在注释里了，欢迎大佬指出错误

C++ 代码

// https://www.bilibili.com/video/BV1zz4y1m7Nq/?spm_id_from=333.337.search-card.all.click&vd_source=76891233b65797af20d50ba389c51d50
// https://www.acwing.com/solution/content/6554/
// 稀疏图的dijkstra：用堆优化
// 此题是稠密图，因此用邻接矩阵
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

// 需要维护距离，用临接表维护距离的时候还需要知道节点的编号，因此用pair对维护距离
typedef pair<int, int> PII; 

const int N = 1000010, INF = 0x3f3f3f3f; // N = 100010的时候会wrong answer

int n, m;
int h[N], w[N], e[N], ne[N], idx; // w表示权重
int dist[N]; // 表示从No_1点到No_i点的(最短)距离
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

int dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    // 小根堆 注意用堆表示最短距离的话可能会存在冗余，一个最短距离存好几次，因此需要用st数组判断当前点的最短距离是否已经求过了
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, 1}); // 把起点1号点放进来更新距离

    while (heap.size())
    {
        // 每次开头找到当前距离最小的那个点
        auto t = heap.top();
        heap.pop();

        // ver表示编号，distance表示距离
        int ver = t.second, distance = t.first;

        if (st[ver]) // 如果ver这个点之前已经出来过了，说明当前这个点是一个冗余备份，就没有必要去处理它了
            continue;
        st[ver] = true; // Dijkstra I的第二步

        // 遍历i点的下一个相邻节点
        for (int i = h[ver]; i != -1; i = ne[i]) // 这个循环最多执行m次，因此队列里最多有m条边
        {
        // j表示下一个节点编号，dist[j]表示原来的初始点到j点的距离，dist[ver]或者distance表示初始点到i点的距离，w[i]表示i点到j点的距离(又叫权重)
            int j = e[i]; // 用j来存储点的编号

            // 下面的if在()后面加;导致wrong answer！！！
            if(dist[j] > dist[ver] + w[i]) // 如果起始点到j点的距离大于从t点过来到j的距离的话就更新一下
            {
                dist[j] = dist[ver] + w[i];//更新距离 Dijkstra I的第三步
                heap.push({dist[j], j});// 把j点放到优先队列里去 Dijkstra I的第一步
            }
        }
    }

    if(dist[n] == INF) return -1; // 说明1和n是不连通的
    else return dist[n];
}

int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);

    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    } 

    int t = dijkstra();

    cout << t << endl;
    return 0;
}