def spfa(n, e):
    from collections import deque 
    q = deque()
    for i in range(n): q.append([0, i])
    dist, cnt = [0] * n, [0] * n
    while q:
        d, u = q.popleft() 
        for dv, v in e[u]:
            if d + dv < dist[v]:
                dist[v], cnt[v] = d + dv, cnt[u] + 1 
                q.append([dist[v], v]) 
                if cnt[v] >= n: return True
    return False