给定一个n个点m条边的有向图，图中可能存在重边和自环，所有边权均为非负值。 请你求出1号点到n号点的最短距离，如果无法从1号点走到n号点，则输出-1。用c++代码实现

注：以下为Dijkstra算法的C语言实现，时间复杂度为O(mlogn)，其中m为边数，n为点数。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>

#define MAXN 100005    // 最大点数
#define MAXM 1000005   // 最大边数

int head[MAXN], nxt[MAXM], to[MAXM], w[MAXM], idx;  // 邻接表存图
int dis[MAXN];      // dis[i]表示1号点到i号点的最短距离
bool vis[MAXN];     // vis[i]表示i号点是否已确定最短路

void add(int u, int v, int c) {  // 添加一条u->v，边权为c的有向边
    nxt[++idx] = head[u];
    head[u] = idx;
    to[idx] = v;
    w[idx] = c;
}

void dijkstra(int s, int n) {   // 求1号点到n号点的最短路
    for (int i = 1; i <= n; i++) {
        dis[i] = INT_MAX;   // 初始距离为无穷大
        vis[i] = false;     // 初始状态为未确定最短路
    }
    dis[s] = 0;             // 1号点到自己的距离为0
    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == 0 || dis[j] < dis[u])) {   // 找到距离未确定最短路的点中距离最小的点
                u = j;
            }
        }
        if (u == n) return;     // 如果当前最小距离的点是n号点，直接返回
        if (dis[u] == INT_MAX) return;  // 无法到达n号点，直接返回-1
        vis[u] = true;          // 确定u号点的最短路
        for (int j = head[u]; j; j = nxt[j]) {  // 更新与u相邻的点的距离
            int v = to[j], c = w[j];
            if (!vis[v] && dis[u] + c < dis[v]) {
                dis[v] = dis[u] + c;
            }
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d %d %d", &u, &v, &c);
        add(u, v, c);     // 添加一条有向边
    }
    dijkstra(1, n);       // 求1号点到n号点的最短路
    if (dis[n] == INT_MAX) {  // 无法到达n号点，输出-1
        printf("-1\n");
    } else {
        printf("%d\n", dis[n]);   // 输出1号点到n号点的最短距离
    }
    return 0;
}

其中，add函数用于添加一条有向边，dijkstra函数用于求1号点到n号点的最短路，核心代码如下：

for (int i = 1; i <= n; i++) {
    int u = 0;
    for (int j = 1; j <= n; j++) {
        if (!vis[j] && (u == 0 || dis[j] < dis[u])) {   // 找到距离未确定最短路的点中距离最小的点
            u = j;
        }
    }
    if (u == n) return;     // 如果当前最小距离的点是n号点，直接返回
    if (dis[u] == INT_MAX) return;  // 无法到达n号点，直接返回-1
    vis[u] = true;          // 确定u号点的最短路
    for (int j = head[u]; j; j = nxt[j]) {  // 更新与u相邻的点的距离
        int v = to[j], c = w[j];
        if (!vis[v] && dis[u] + c < dis[v]) {
            dis[v] = dis[u] + c;
        }
    }
}

具体实现过程详见注释。