def spfa(n, e, s): 
    from collections import deque
    dist = [10 ** 8] * n 
    q = deque([[0, s]]) 
    while q:
        d, u = q.popleft()
        if d >= dist[u]: continue
        dist[u] = d 
        for dv, v in e[u]: q.append([d + dv, v])
    return dist