热浪

#include <bits/stdc++.h>
#define N 25001
#define M 62001
using namespace std;

struct Edge {
    int x, y, z, next;
    Edge(int x = 0, int y = 0, int z = 0, int next = 0) :
        x(x), y(y), z(z), next(next) {}
} edge[M * 2];

int n, m, s, t, sumedge, head[N];
bool vis[N];
int inn[N], dis[N];

void ins(int x, int y, int z) {
    edge[++sumedge] = Edge(x, y, z, head[x]);
    head[x] = sumedge;
    return;
}

bool SPFA(int x) {
    queue<int> q;
    memset(dis, 0x3f, sizeof dis);
    memset(vis, false, sizeof vis);
    memset(inn, 0, sizeof inn);
    dis[x] = 0;
    q.push(x);
    vis[x] = 1;
    inn[x] = 1;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        vis[t] = 0;
        for (int u = head[t]; u; u = edge[u].next) {
            int temp = edge[u].y;
            if (dis[temp] > dis[t] + edge[u].z) {
                dis[temp] = dis[t] + edge[u].z;
                if (!vis[temp]) {
                    vis[temp] = 1;
                    inn[temp]++;
                    q.push(temp);
                    if (inn[temp] > n) return false;
                }
            }
        }
    }
    return true;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        ins(x, y, z);
        ins(y, x, z);
    }

    if (SPFA(s)) printf("%d", dis[t]);
    return 0;
}