void spfa(int start, int d[]) {
    deque<int> q;
    memset(d, 0x3f, 4 * N);
    d[start] = 0;
    v[start] = true;
    q.push_back(start);
    int sum = d[start], num = 1;
    while (q.size()) {
        int x = q.front();
        while (d[x] * num > sum) {
            q.pop_front();
            q.push_back(x);
            x = q.front();
        }
        q.pop_front();
        sum -= d[x];
        num--;
        v[x] = false;
        for (int i = head[x]; i; i = nxt[i]) {
            int y = ver[i], z = edge[i];
            if (d[y] > d[x] + z) {
                d[y] = d[x] + z;
                if (!v[y]) {
                    if (q.size() && d[y] > d[q.front()])
                        q.push_back(y);
                    else
                        q.push_front(y);
                    sum += d[y];
                    num++;
                    v[y] = true;
                }
            }
        }
    }
}