Graveyard problem TIME EXCEEDED

That's my first problem here. I just pressed Random button and got it. Graveyard problem.2 After reading I felt that it was all about Bellman-Ford algorithm. It just solves all the needed problems. So I wrote a straightforward solution but I got Time Exceeded Error on the first test. Now I'm not clearly sure what's the problem.

As I said it's my first task here therefore I should ask if it is possible that something is wrong with reading input? On my PC I run program with:

`cat input | python graveyard.py`

Where input contains the example presented on the problem page.

Or there is a secret way to optimize the solution?

So here is my code, I tried to comment it well.
Thanks!

 # If dist[v] == UNAWARED than there is no way to v
UNAWARED = 1000000000000

# Cost to travel to neighbor cell
FREE_COST = 1

# initial position
ENTRANCE = (0, 0)

deltas = [[0, 1],
          [0, -1],
          [1, 0],
          [-1, 0]]


def check_delta(shape, pos, delta):
    """
    If it's possible to get from pos to pos+delta then
        return pos+delta, otherwise return None
    """
    x_new = pos[0] + delta[0]
    y_new = pos[1] + delta[1]

    if (x_new < 0) or (x_new >= shape[0]):
        return None

    if (y_new < 0) or (y_new >= shape[1]):
        return None

    return x_new, y_new


def pos_to_v(shape, pos):
    """
    Translates map coordinates to graph vertex number

    shape        ---    size of map (h, w)
    """
    return pos[0]*shape[1] + pos[1]


def build_edges():
    """
    Create edges graph representation

    Firstly it creates graph with all the neighbors connected
    Then when reading gravestone and holes it removes/add connections

    edges[v]        --- all edges which are incident with v
    edges[v][i][0]  --- destination vertex
    edges[v][i][1]  --- weight to travel from v to destination(1 for grass, t for hole)

    shape           --- shape of graveyard

    if shape == (0, 0)  (end of test cases)
        return None
    otherwise
        return edges, shape
    """
    shape = [int(x) for x in raw_input().split(' ')]

    if (shape[0] == 0) and (shape[1] == 0):
        return None

    v_num = (shape[0]*shape[1])
    edges = [0]*v_num

    # Build graph with all neighbors connected
    for v in range(v_num):
        i = int(v / shape[1])
        j = int(v % shape[1])

        subedges = list()

        for d in deltas:
            new_pos = check_delta(shape, (i,j), d)

            if new_pos:
                new_v = pos_to_v(shape, new_pos)
                subedges.append((new_v, FREE_COST))

        edges[v] = subedges

    gravestones = int(raw_input())

    # All paths from/to gravestone tile are being removed
    for i in range(gravestones):
        grave_pos = [int(x) for x in raw_input().split(' ')]
        v = pos_to_v(shape, grave_pos)

        # Iteratively remove edges from v and
        # edges from destination vertex to v
        while len(edges[v]) > 0:
            e = edges[v].pop(0)
            edges[e[0]].remove((v, FREE_COST))

    holes = int(raw_input())

    # All paths from hole tile are being removed
    # Path from hole to destination is being added
    for i in range(holes):
        hole_info = [int(x) for x in raw_input().split(' ')]
        hole_pos = hole_info[0:2]
        hole_dest = hole_info[2:4]
        hole_time = hole_info[4]

        v = pos_to_v(shape, hole_pos)
        d = pos_to_v(shape, hole_dest)

        edges[v] = [[d, hole_time]]

    return edges, shape


def ford_bellman(edges, dist):
    """
    Just a Bellman-Ford algorithm

    If negative cycle is found then return None otherwise
        return an array of distances
    """
    l = len(edges)

    for relax in range(l):
        for v in range(l):
            for i in range(len(edges[v])):
                new_dist = dist[v] + edges[v][i][1]

                if dist[edges[v][i][0]] > new_dist:
                    dist[edges[v][i][0]] = new_dist

    for v in range(l):
        for i in range(len(edges[v])):
            if dist[v] + edges[v][i][1] < dist[edges[v][i][0]]:
                return None

    return dist


if __name__ == "__main__":
    graph = build_edges()

    while graph:
        edges = graph[0]
        shape = graph[1]

        EXIT = (shape[0]-1, shape[1]-1)

        # Initially fill all distances with infinity
        # Only starting position has distance 0
        dist = [UNAWARED]*(shape[0]*shape[1])
        dist[pos_to_v(shape, ENTRANCE)] = 0

        # Find shortest paths
        dist = ford_bellman(edges, dist)

        # Print result
        if not dist:
            print("Never")

        elif dist[pos_to_v(shape, EXIT)] == UNAWARED:
            print("Impossible")

        else:
            print(str(dist[pos_to_v(shape, EXIT)]))

        graph = build_edges()