Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [maxint] * num
    weight[0] = 0
    V = set(xrange(1, num))
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v] = min(weight[v], cost + weight[index])

        index = min(V, key=lambda i: weight[i])
        V.remove(index)

    for i, d in enumerate(weight):
        print(i, d)


main()

Fixed submission:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [maxint] * num
    weight[0] = 0
    V = set(xrange(1, num))
    index = 0

    def compare(i):
        return weight[i]

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v] = min(weight[v], cost + weight[index])

        index = min(V, key=compare)
        V.remove(index)

    for i, d in enumerate(weight):
        print(i, d)


main()

Fixed submission:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
from operator import itemgetter


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[i, maxint] for i in xrange(num)]
    weight[0][1] = 0
    V = set(xrange(1, num))
    W = weight[1:]
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v][1] = min(weight[v][1], cost + weight[index][1])

        W.sort(key=itemgetter(1), reverse=True)
        index = W.pop()[0]

        V.remove(index)

    for i, d in weight:
        print(i, d)


main()

Fixed submission:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
import heapq


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    W = weight[:]
    heapq.heappop(W)
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v][0] = min(weight[v][0], cost + weight[index][0])

        heapq.heapify(W)
        index = heapq.heappop(W)[1]
        V.remove(index)

    for d, i in weight:
        print(i, d)


main()

Fixed submission:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint


def max_heapify(heap, i, heap_size):
    L = i * 2
    R = L + 1
    if L <= heap_size and heap[L][0] < heap[i][0]:
        largest = L
    else:
        largest = i
    if R <= heap_size and heap[R][0] < heap[largest][0]:
        largest = R
    if largest != i:
        heap[i], heap[largest] = heap[largest], heap[i]
        max_heapify(heap, largest, heap_size)


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    W = weight[:]
    wn = num
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v][0] = min(weight[v][0], cost + weight[index][0])

        for i in xrange(wn//2, 0, -1):
            max_heapify(W, i, wn-1)
        index = W[1][1]
        W[1] = W[-1]
        wn -= 1
        del W[-1]
        V.remove(index)

    for d, i in weight:
        print(i, d)


main()

Fixed submission:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
from operator import itemgetter


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    W = weight[1:]
    index = 0

    while V:
        for v, cost in L[index]:
            if v not in V:
                continue
            weight[v][0] = min(weight[v][0], cost + weight[index][0])

        a = min(W, key=itemgetter(0))
        index = a[1]
        W.remove(a)
        V.remove(index)

    for d, i in weight:
        print(i, d)


main()

Fixed submission:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
import heapq


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    W = weight[1:]
    index = 0

    while V:
        swap = False
        for v, cost in L[index]:
            if v not in V:
                continue
            cost += weight[index][0]
            if weight[v][0] > cost:
                weight[v][0] = cost
                swap = True

        if swap:
            heapq.heapify(W)
        index = heapq.heappop(W)[1]
        V.remove(index)

    for d, i in weight:
        print(i, d)


main()

Fixed submission:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
from operator import itemgetter
import heapq


def main():
    num = int(stdin.readline())

    L = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        L.append([(next(it), next(it)) for _ in xrange(next(it))])

    weight = [[maxint, i] for i in xrange(num)]
    weight[0][0] = 0
    V = set(xrange(1, num))
    A = set(v for v, cost in L[0])
    W = weight[1:]
    index = 0

    while V:
        swap = False
        for v, cost in L[index]:
            if v not in A:
                continue
            weight[v][0] = min(weight[v][0], cost + weight[index][0])


        a = min(W, key=itemgetter(0))
        index = a[1]
        W.remove(a)

        A.update(v for v, cost in L[index])
        A.remove(index)
        V.remove(index)

    for d, i in weight:
        print(i, d)


main()

Fixed submission:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxint
from operator import itemgetter
from heapq import heappush, heappop, heapify


def main():
    num = int(stdin.readline())

    edges = []
    for _ in xrange(num):
        it = iter(int(s) for s in stdin.readline().split()[1:])
        edges.append([(next(it), next(it)) for _ in xrange(next(it))])

    distances = [[maxint, i] for i in xrange(num)]
    distances[0][0] = 0
    V = set(xrange(1, num))
    W = []#distances[1:]
    mark = set()
    index = 0

    while V:
        for v, cost in edges[index]:
            if v not in V:
                continue
            cost += distances[index][0]
            if distances[v][0] > cost:
                distances[v][0] = cost
                if v not in mark:
                    W.append(distances[v])
                    mark.add(v)

        a = min(W, key=itemgetter(0))
        index = a[1]
        W.remove(a)
        mark.remove(index)
        V.remove(index)

    for d, i in distances:
        print(i, d)

main()

Fixed submission:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, maxsize


def main():
    num = int(stdin.readline())

    edges = []
    for _ in range(num):
        ns = [int(s) for s in stdin.readline().split()]
        for i in range(ns[1]):
            edges.append((ns[0], ns[2*i+2], ns[2*i+3]))

    dis = [maxsize] * num
    dis[0] = 0

    while 1:
        update = False
        for from_, to, cost in edges:
            if dis[from_] < maxsize and dis[to] > cost + dis[from_]:
                dis[to] = cost + dis[from_]
                update = True

        if not update:
            break

    for i, d in enumerate(dis):
        print(i, d)


main()