# TRITIUM-PROVENANCE sha256=cecf307e190155d45c2cc7a93a750de16f8670bcbb0f247d9967748079f4e335 lang=python
# TRITIUM-HEIGHT high=0.12 mid=0.20 low=0.68 fns=14
# TRITIUM-PSEUDO fn=fill_list
#| fn fill_list(vals, n, v):
#|   return 0
# TRITIUM-HEIGHT fn=fill_list high=0.00 mid=0.34 low=0.66 role=mid_helper
def fill_list(vals, n, v):
    i = 0
    while i < n:
        vals[i] = v
        i = i + 1
    return 0

# TRITIUM-PSEUDO fn=sift_up
#| fn sift_up(heap_dist, heap_node, i):
#|   return i
# TRITIUM-HEIGHT fn=sift_up high=0.00 mid=0.31 low=0.69 role=mid_helper
def sift_up(heap_dist, heap_node, i):
    while i > 0:
        p = (i - 1) // 2
        if heap_dist[i] >= heap_dist[p]:
            break
        tmp_dist = heap_dist[i]
        heap_dist[i] = heap_dist[p]
        heap_dist[p] = tmp_dist
        tmp_node = heap_node[i]
        heap_node[i] = heap_node[p]
        heap_node[p] = tmp_node
        i = p
    return i

# TRITIUM-PSEUDO fn=sift_down
#| fn sift_down(heap_dist, heap_node, last):
#|   return i
# TRITIUM-HEIGHT fn=sift_down high=0.00 mid=0.43 low=0.57 role=mid_helper
def sift_down(heap_dist, heap_node, last):
    i = 0
    while True:
        l = i * 2 + 1
        r = l + 1
        if l > last:
            break
        m = l
        if r <= last and heap_dist[r] < heap_dist[l]:
            m = r
        if heap_dist[i] <= heap_dist[m]:
            break
        tmp_dist = heap_dist[i]
        heap_dist[i] = heap_dist[m]
        heap_dist[m] = tmp_dist
        tmp_node = heap_node[i]
        heap_node[i] = heap_node[m]
        heap_node[m] = tmp_node
        i = m
    return i

# TRITIUM-PSEUDO fn=dist_init
#| fn dist_init(dist, n, start, inf):
#|   fill_list(dist, n, inf)
#|   dist[start] = 0
#|   return 0
# TRITIUM-HEIGHT fn=dist_init high=0.38 mid=0.12 low=0.50
def dist_init(dist: list[int], n: int, start: int, inf: int) -> int:
    fill_list(dist, n, inf)
    dist[start] = 0
    return 0

# TRITIUM-PSEUDO fn=heap_push
#| fn heap_push(hd, hu, n, d, u):
#|   hd[n] = d
#|   hu[n] = u
#|   sift_up(hd, hu, n)
#|   return n + 1
# TRITIUM-HEIGHT fn=heap_push high=0.23 mid=0.15 low=0.61
def heap_push(hd: list[int], hu: list[int], n: int, d: int, u: int) -> int:
    hd[n] = d
    hu[n] = u
    sift_up(hd, hu, n)
    return n + 1

# TRITIUM-PSEUDO fn=heap_min_d
#| fn heap_min_d(hd, hu, n):
#|   return hd[0]
# TRITIUM-HEIGHT fn=heap_min_d high=0.00 mid=0.00 low=1.00 role=algo_mid
def heap_min_d(hd: list[int], hu: list[int], n: int) -> int:
    return hd[0]

# TRITIUM-PSEUDO fn=heap_min_u
#| fn heap_min_u(hd, hu, n):
#|   return hu[0]
# TRITIUM-HEIGHT fn=heap_min_u high=0.00 mid=0.00 low=1.00 role=algo_mid
def heap_min_u(hd: list[int], hu: list[int], n: int) -> int:
    return hu[0]

# TRITIUM-PSEUDO fn=heap_pop
#| fn heap_pop(hd, hu, n):
#|   sift_down(...)
#|   return last
# TRITIUM-HEIGHT fn=heap_pop high=0.17 mid=0.17 low=0.67
def heap_pop(hd: list[int], hu: list[int], n: int) -> int:
    last = n - 1
    hd[0] = hd[last]
    hu[0] = hu[last]
    sift_down(hd, hu, last - 1)
    return last

# TRITIUM-PSEUDO fn=list_get
#| fn list_get(vals, i):
#|   return vals[i]
# TRITIUM-HEIGHT fn=list_get high=0.00 mid=0.00 low=1.00 role=algo_mid
def list_get(vals: list[int], i: int) -> int:
    return vals[i]

# TRITIUM-PSEUDO fn=stale_visit
#| fn stale_visit(dist, u, d):
#|   return int(d > list_get(dist, u))
# TRITIUM-HEIGHT fn=stale_visit high=0.00 mid=0.43 low=0.57
def stale_visit(dist: list[int], u: int, d: int) -> int:
    return int(d > list_get(dist, u))

# TRITIUM-PSEUDO fn=relax_edge
#| fn relax_edge(dist, hd, hu, heap_len, u, v, w):
#|   new_dist = dist[u] + w
#|   if new_dist < dist[v]:
#|     dist[v] = new_dist
#|     heap_len = heap_push(hd, hu, heap_len, new_dist, v)
#|   return heap_len
# TRITIUM-HEIGHT fn=relax_edge high=0.15 mid=0.27 low=0.58 role=algo_mid
def relax_edge(dist: list[int], hd: list[int], hu: list[int], heap_len: int, u: int, v: int, w: int) -> int:
    new_dist = dist[u] + w
    if new_dist < dist[v]:
        dist[v] = new_dist
        heap_len = heap_push(hd, hu, heap_len, new_dist, v)
    return heap_len

# TRITIUM-PSEUDO fn=edge_relax
#| fn edge_relax(dist, hd, hu, heap_len, dest, weight, e, u):
#|   v = list_get(dest, e)
#|   w = list_get(weight, e)
#|   return relax_edge(dist, hd, hu, heap_len, u, v, w)
# TRITIUM-HEIGHT fn=edge_relax high=0.18 mid=0.21 low=0.61
def edge_relax(dist: list[int], hd: list[int], hu: list[int], heap_len: int, dest: list[int], weight: list[int], e: int, u: int) -> int:
    v = list_get(dest, e)
    w = list_get(weight, e)
    return relax_edge(dist, hd, hu, heap_len, u, v, w)

# TRITIUM-PSEUDO fn=scan_neighbors
#| fn scan_neighbors(dist, hd, hu, heap_len, dest, weight, offsets, u):
#|   edge_relax(...)
#|   return heap_len
# TRITIUM-HEIGHT fn=scan_neighbors high=0.12 mid=0.23 low=0.65
def scan_neighbors(dist: list[int], hd: list[int], hu: list[int], heap_len: int, dest: list[int], weight: list[int], offsets: list[int], u: int) -> int:
    e = list_get(offsets, u)
    end = list_get(offsets, u + 1)
    while e < end:
        heap_len = edge_relax(dist, hd, hu, heap_len, dest, weight, e, u)
        e = e + 1
    return heap_len

# TRITIUM-PSEUDO fn=dijkstra
#| fn dijkstra(n, offsets, dest, weight, start, dist, hd, hu):
#|   dist_init(...)
#|   heap_push(...)
#|   heap_min_d(...)
#|   heap_min_u(...)
#|   heap_pop(...)
#|   scan_neighbors(...)
#|   stale_visit(...)
#|   return 0
# TRITIUM-HEIGHT fn=dijkstra high=0.46 mid=0.19 low=0.35
def dijkstra(n: int, offsets: list[int], dest: list[int], weight: list[int], start: int, dist: list[int], hd: list[int], hu: list[int]) -> int:
    inf = 1000000000
    dist_init(dist, n, start, inf)
    heap_len = heap_push(hd, hu, 0, 0, start)
    while heap_len > 0:
        d = heap_min_d(hd, hu, heap_len)
        u = heap_min_u(hd, hu, heap_len)
        heap_len = heap_pop(hd, hu, heap_len)
        if stale_visit(dist, u, d) == 1:
            continue
        heap_len = scan_neighbors(dist, hd, hu, heap_len, dest, weight, offsets, u)
    return 0