最优解（167行）

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

#define MAXN 2001    // 城市数量上限
#define MAXM 10001   // 道路数量上限

// 邻接表节点结构
typedef struct Edge {
    int to;          // 目标城市
    int weight;      // 道路长度
    struct Edge* next; // 下一条边
} Edge;

// 优先队列节点结构（用于Dijkstra算法优化）
typedef struct Node {
    int distance;    // 当前距离
    int city;        // 城市编号
} Node;

// 全局变量
Edge* adj[MAXN];    // 邻接表
int dist[MAXN];     // 距离数组，dist[i]表示1到i的最短距离
int visited[MAXN];  // 标记是否已确定最短路径

// 小根堆相关函数
void swap(Node* a, Node* b) {
    Node temp = *a;
    *a = *b;
    *b = temp;
}

// 堆化（向上调整）
void heapifyUp(Node heap[], int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[parent].distance <= heap[index].distance) break;
        swap(&heap[parent], &heap[index]);
        index = parent;
    }
}

// 堆化（向下调整）
void heapifyDown(Node heap[], int size, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    
    if (left < size && heap[left].distance < heap[smallest].distance)
        smallest = left;
    if (right < size && heap[right].distance < heap[smallest].distance)
        smallest = right;
    
    if (smallest != index) {
        swap(&heap[index], &heap[smallest]);
        heapifyDown(heap, size, smallest);
    }
}

// 插入元素到堆
void push(Node heap[], int* size, int distance, int city) {
    heap[*size].distance = distance;
    heap[*size].city = city;
    heapifyUp(heap, *size);
    (*size)++;
}

// 弹出堆顶元素
Node pop(Node heap[], int* size) {
    Node top = heap[0];
    (*size)--;
    heap[0] = heap[*size];
    heapifyDown(heap, *size, 0);
    return top;
}

// 添加边到邻接表
void addEdge(int from, int to, int weight) {
    Edge* edge = (Edge*)malloc(sizeof(Edge));
    edge->to = to;
    edge->weight = weight;
    edge->next = adj[from];
    adj[from] = edge;
}

// Dijkstra算法实现
void dijkstra(int n) {
    // 初始化距离数组
    for (int i = 1; i <= n; i++) {
        dist[i] = INT_MAX;
        visited[i] = 0;
    }
    dist[1] = 0;  // 起点距离为0
    
    // 优先队列（小根堆）
    Node heap[2 * MAXM];
    int heapSize = 0;
    push(heap, &heapSize, 0, 1);
    
    while (heapSize > 0) {
        // 取出距离最小的城市
        Node current = pop(heap, &heapSize);
        int u = current.city;
        
        // 若已确定最短路径，跳过
        if (visited[u]) continue;
        visited[u] = 1;
        
        // 若到达终点，可提前退出
        if (u == n) break;
        
        // 遍历所有相邻城市
        Edge* edge = adj[u];
        while (edge != NULL) {
            int v = edge->to;
            int weight = edge->weight;
            
            // 松弛操作：更新距离
            if (!visited[v] && dist[u] != INT_MAX && dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                push(heap, &heapSize, dist[v], v);
            }
            
            edge = edge->next;
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    // 初始化邻接表
    for (int i = 1; i <= n; i++) {
        adj[i] = NULL;
    }
    
    // 读取道路信息（无向图，双向添加）
    for (int i = 0; i < m; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        addEdge(a, b, c);
        addEdge(b, a, c);
    }
    
    // 执行Dijkstra算法
    dijkstra(n);
    
    // 输出结果
    if (dist[n] == INT_MAX) {
        printf("-1\n");  // 无法到达
    } else {
        printf("%d\n", dist[n]);  // 最短距离
    }
    
    // 释放内存
    for (int i = 1; i <= n; i++) {
        Edge* edge = adj[i];
        while (edge != NULL) {
            Edge* temp = edge;
            edge = edge->next;
            free(temp);
        }
    }
    
    return 0;
}