#G = [[1, [(1,5), (6,8), (5, 9), (7 (premier depart), 11 (première arrivée), 3 (période), 31(dernier depart)), (8, (marche))]], [2, ]]


def chemin_valide(chemin,u,v,t):
    n = len(chemin)
    if u!= chemin[0][0] or t > chemin[0][2] or v!=chemin[n-1][1]:
        return False
    for i in range(n-1):
        u1, v1, td1, ta1 = chemin[i]
        u2, v2, td2, ta2 = chemin[i+1]
        if v1 != u2 or ta1 > td2:
            return False
    return True

horaires_0_1 = [(3,10), (7, 15), (9, 16), (15, 22)]

horaires_0_2 = [(2, 5, 12, 50), (11,)]

horaires_1_2 = [(1,5), (6,8), (5, 9), (7, 11, 4, 31), (6,)]

horaires_1_3 = [(1,20), (10,30), (21,32), (3, 28, 5, 48)]

horaires_1_4 = [(6,10), (18, 22), (28, 33), (40, 44), (12,)]

horaires_2_1 = [(3,7), (6,8), (13,15), (2, 6, 4, 38), (6,)]

horaires_2_4 = [(4, 11, 10, 54)]

horaires_3_4 = [(3, 10), (10, 18), (22, 31), (35, 44)]

horaires_4_3 = [(6, 14, 10, 46)]

Z = horaires_0_2[0]

G = [
[(1, horaires_0_1), (2, horaires_0_2)],
[(2, horaires_1_2), (3, horaires_1_3), (4, horaires_1_4)],
[(1, horaires_2_1), (4, horaires_2_4)],
[(4, horaires_3_4)],
[(3, horaires_4_3)]]



def meilleur_horaire(horaires, t):
    td = ta = float("inf")
    for L in horaires:
        if len(L) == 2: #trajet ponctuel
            t1, t2 = L
            if t1 >= t and t2 < ta:
                td = t1
                ta = t2
        elif len(L) == 1: #marche
            t2 = t + L[0]
            if t2 < ta:
                td = t
                ta = t2
        else: #trajet periodique
            premier_depart, premiere_arrivee, periode, dernier_depart = L
            if t <= dernier_depart:
                gap = (t - premier_depart)%periode
                if t < premier_depart:
                    t1 = premier_depart
                elif gap == 0:
                    t1 = t
                else:
                    t1 = t - gap + periode
                t2 = t1 + premiere_arrivee - premier_depart
                if t2 < ta:
                    td = t1
                    ta = t2
    return td, ta

def dijkstra_temporel(G, s, t_dep):
    n = len(G)
    marque = [False]*n
    T = [float("inf")]*n
    T[s] = t_dep
    P = [None]*n
    for _ in range(n):
        t_min = float("inf")
        for i in range(n):
            if not marque[i] and T[i] < t_min:
                t_min = T[i]
                u = i
        marque[u] = True
        for v, horaires in G[u]:
            td, ta = meilleur_horaire(horaires, T[u])
            if ta < T[v]:
                T[v] = ta
                P[v] = (u, td, ta)
        print(u)
        print(T)
        print(P)
    return T, P

def chemin(P, u):
    if P[u] == None:
        return []
    pred_u, td, ta = P[u]
    L = chemin(P, pred_u)
    L.append((pred_u, u, td, ta))
    return L