本来想写堆优化Dij的，结果写着写着写成spfa了，中间还没意识到，写完才发现，这手不听使唤啊。

#include<bits/stdc++.h>
using namespace std;
const int N = 150010,M = 150010,INF = 2e9;
int n,m;
int h[N],e[M],w[M],ne[M],idx;
int dis[N];
bool st[N];
void add(int a,int b,int c)
{
    w[idx] = c,e[idx] = b;ne[idx] = h[a],h[a] = idx++;
}
int main()
{
    memset(h,-1,sizeof h);
    cin >> n >> m;
    for (int i = 0; i < m;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        if (a!=b)
            add(a,b,c);
    }

    memset(st,0,sizeof st);
    fill(dis,dis + N,INF);
    queue<int> q;
    q.push(1);
    st[1] = true;
    dis[1] = 0;
    while (q.size())
    {
        int u = q.front();
        q.pop();
        st[u] = false;
        for (int i = h[u];~i;i = ne[i])
        {
            int j = e[i];
            if (dis[j] > dis[u] + w[i])
            {
                dis[j] = dis[u] + w[i];
                if (!st[j]) 
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
    if (dis[n] >= INF) cout << -1;
    else cout << dis[n];
    return 0;
}