文件目录

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int v; // 目的地
    int w; // 权重
};
vector<edge> graph[100005]; // 邻接表
int a, b, c, n, m;
int dis[100005];  // 记录从起点到达各个顶点的最短距离
bool inq[100005]; // 记录队列中的点
void spfa(int start)
{
    memset(inq, 0, sizeof(inq));
    memset(dis, 0x3f, sizeof(dis));
    queue<int> q; // 正在查询的点集
    q.push(start);
    dis[start] = 0;
    inq[start] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        inq[u] = 0; // graph[u]
        for (int i = 0; i < graph[u].size(); i++)
        {
            int v = graph[u][i].v;
            int w = graph[u][i].w;
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if (!inq[v])
                {
                    q.push(v);
                    inq[v] = 1;
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d", &n, &m);
    // cin>>n>>m;
    while (m--)
    {
        // cin>>a>>b>>c;
        scanf("%d %d %d", &a, &b, &c);
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }
    spfa(1);
    cout << dis[n];
    return 0;
}