Buggy python submission (verdict: Runtime Error):
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    return d
'''
result = Dijkstra(r, vertex)
for i in range(vertex):
    if i == r:
        result[i] = 0
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])



Fixed submission:
# Single Source Shortest Path
import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])

Buggy python submission (verdict: Runtime Error):
from memory_profiler import profile
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

@profile
def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    del visited_order
    del label
    del D
    del min_cost

    d[root] = 0
    return d

result = Dijkstra(r, vertex)

for i in range(vertex):
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])




Fixed submission:
# Single Source Shortest Path
import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])

Buggy python submission (verdict: Runtime Error):
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
D = [[infty for j in range(vertex)] for i in range(vertex)]
for i in range(edge):
    data = list(map(int, input("").split()))
    D[data[0]][data[1]] = data[2]

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global D
    global infty
    d = D[root]
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > d[i]:
                min_cost = d[i]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if d[i] > d[min_node] + D[min_node][i]:
                d[i] = d[min_node] + D[min_node][i]

    del visited_order
    del label
    del D
    del min_cost

    d[root] = 0
    return d

result = Dijkstra(r, vertex)

for i in range(vertex):
    if result[i] == infty:
        result[i] = "INF"
    print(result[i])




Fixed submission:
# Single Source Shortest Path
import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])

Buggy python submission (verdict: Runtime Error):
# Single Source Shortest Path
infty = 99999

[vertex, edge, r] = list(map(int, input("").split()))
dict_r = {}
for i in range(vertex):
    dict_r[(r,i)] = infty

dict_c = {}
for i in range(edge):
    data = list(map(int, input("").split()))
    if int(data[0]) == r:
        dict_r[(data[0],data[1])] = int(data[2])
    else:
        dict_c[(data[0],data[1])] = int(data[2])
del data

def Dijkstra(root, n):
    visited_order = 0
    label = [0 for i in range(n)]
    global dict_r, dict_c, infty
    visited_order += 1
    label[root] = visited_order

    while visited_order < n:
        min_cost = infty

        for i in range(n):
            if label[i] != 0:
                continue

            if min_cost > dict_r[(root, i)]:
                min_cost = dict_r[(root, i)]
                min_node = i

        if min_cost == infty:
            break

        visited_order += 1
        label[min_node] = visited_order

        for i in range(n):
            if label[i] != 0:
                continue
            if ((min_node, i) in dict_c.keys()) == True:
                if dict_r[(root, i)] > dict_r[(root, min_node)] + dict_c[(min_node, i)]:
                    dict_r[(root, i)] = dict_r[(root, min_node)] + dict_c[(min_node, i)]

Dijkstra(r, vertex)

for i in range(vertex):
    if r == i:
        print(0)
    elif dict_r[(r, i)] == infty:
        print("INF")
    else:
        print(dict_r[(r, i)])



Fixed submission:
# Single Source Shortest Path
import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])

Buggy python submission (verdict: Time Limit Exceeded):
# Single Source Shortest Path
class node():
    def __init__(self, v, cost):
        self.v = v
        self.cost = cost

infty = 999999999
dict_c = {}
[vertex, edge, r] = list(map(int, input("").split()))
root_c = [node(r, 0)]
final_c = [infty for i in range(vertex)]
final_c[r] = 0

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    if e1 == r:
        root_c.append(node(e2, c))
        final_c[e2] = c
    else:
        dict_c[(e1, e2)] = c

def min_heap(i):
    global root_c
    l = 2*i
    r = 2*i + 1
    if l <= len(root_c) - 1 and root_c[l].cost <= root_c[i].cost:
        if root_c[l].cost < root_c[i].cost:
            min = l
        elif root_c[l].v < root_c[i].v:
            min = l
        else:
            min = i
    else:
        min = i
    if r <= len(root_c) - 1 and root_c[r].cost <= root_c[min].cost:
        if root_c[r].cost < root_c[min].cost:
            min = r
        elif root_c[r].v < root_c[min].v:
            min = r
        #else:

    if min != i:
        root_c[i], root_c[min] = root_c[min], root_c[i]
        min_heap(min)

def build_min_heap():
    global root_c
    length = len(root_c) - 1
    for i in range(int(length/2), 0, -1):
        min_heap(i)

def extract_min():
    global root_c
    min = root_c[1]

    #print("min_cost  ", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost, root_c[7].cost)
    #print("min_vertex", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v, root_c[7].v)

    root_c[1] = root_c[len(root_c) - 1]

    #print("1: ",root_c[1].cost, root_c[1].v)

    del root_c[len(root_c) - 1]
    min_heap(1)

    #print("min_cost  2", root_c[1].cost, root_c[2].cost, root_c[3].cost, root_c[4].cost, root_c[5].cost, root_c[6].cost)
    #print("min_vertex2", root_c[1].v, root_c[2].v, root_c[3].v, root_c[4].v, root_c[5].v, root_c[6].v)
    #print("length: ",len(root_c))

    return min

def decrease_key(i, c):
    global root_c
    root_c[i].cost = c
    while i > 1 and root_c[int(i/2)].cost >= root_c[i].cost:
        if root_c[int(i/2)].cost > root_c[i].cost:
            root_c[int(i/2)], root_c[i] = root_c[i], root_c[int(i/2)]
        elif root_c[int(i/2)].v > root_c[i].v:
            root_c[int(i/2)], root_c[i] = root_c[i], root_c[int(i/2)]
        else:
            root_c[int(i/2)], root_c[i] = root_c[int(i/2)], root_c[i]
        i = int(i/2)

def min_insert(v, c):
    global infty, root_c
    for i in range(1, len(root_c)):
        if root_c[i].v == v:
            decrease_key(i,c)
            return

    root_c.append(node(v, infty))
    decrease_key(len(root_c) - 1, c)

def Dijkstra(root, n):

    count = 1

    global infty, dict_c, root_c, final_c
    label = [i for i in range(n)]

    #print(count, label[root], final_c[label[root]])
    count += 1

    del label[root]

    while len(label) != 0:
        if len(root_c) > 1:
            min_node = extract_min()
        else:
            break

        for i in range(len(label)):
            if min_node.v == label[i]:
                delete_label = i
                continue

            if ((min_node.v, label[i]) in dict_c.keys()) == True:
                if final_c[label[i]] > final_c[min_node.v] + dict_c[(min_node.v, label[i])]:
                    final_c[label[i]] = final_c[min_node.v] + dict_c[(min_node.v, label[i])]
                    min_insert(label[i], final_c[label[i]])

        #print(count, label[delete_label], final_c[label[delete_label]])
        count += 1

        del label[delete_label]

build_min_heap()

'''
print("root_c :")
for i in range(len(root_c)):
    print(root_c[i].cost)
print("\n")
'''

Dijkstra(r, vertex)

#print("\n")

for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])



Fixed submission:
# Single Source Shortest Path
import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])