int dis[maxn], cnt[maxn];
bool vis[maxn];

int spfa(){
    queue<int> q;
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    memset(cnt, 0, sizeof(cnt));

    dis[1] = 0;
    vis[1] = 1;
    q.push(1);

    while(q.size()){
        int x = q.front();
        vis[x] = 0;
        q.pop();

        for(int i = head[x]; i; i = Next[i]){
            int y = ver[i], z = edge[i];
            if(dis[y] > dis[x] + z){
                dis[y] = dis[x] + z;
                cnt[y] ++;
                if(cnt[y] > n) return -1; //有负环
                if(!vis[y]){
                    vis[y] = 1;
                    q.push(y);
                }
            }
        }
    }
}