bool ford_bellman(int n, int s, int *d, vector<ford_edge> &ed, vector<int> &p = vector<int>(N,-1)){
    for(int i = 0; i < n; ++i)
        d[i] = INF;
    d[s] = 0;
    bool any = 0;
    int anykek = -1;
    for(int i = 0; i < n; ++i){
        for(const auto& e: ed){
            if(d[e.a]<INF&&d[e.a]+e.w<d[e.b]) d[e.b] = d[e.a]+e.w, p[e.b] = e.a, any = true, anykek = ed.b;
        }
    }
    if(any){
        d[anykek] = -INF;
        for(int i = 0; i < n; ++i){
            for(const auto& e: ed){
                if(d[e.a]<INF&&d[e.a]==-INF) d[e.b] = -INF, p[e.b] = e.a;
            }
        }
    }
    }