Buggy python submission (verdict: Runtime Error):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)
            # キューに格納されている最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                if not (v,i) in self.edges: continue

                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d


if __name__ == "__main__":
    djk = Dijkstra()
    V, E, s = list(map(int, input().split()))
    for i in range(E):
        _from, to, cost = list(map(int, input().split()))
        djk.add(_from, to, cost)

    d = djk.shortest_path(s)
    
    for cost in d:
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Runtime Error):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)
            # キューに格納されている最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                if not (v,i) in self.edges: continue

                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d


if __name__ == "__main__":
    djk = Dijkstra()
    V, E, s = list(map(int, input().split()))
    if E == 0:
        print(0)
    
    for i in range(E):
        _from, to, cost = list(map(int, input().split()))
        djk.add(_from, to, cost)

    d = djk.shortest_path(s)
    
    for cost in d:
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Runtime Error):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)
            # キューに格納されている最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                if not (v,i) in self.edges: continue

                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d


if __name__ == "__main__":
    djk = Dijkstra()
    V, E, s = list(map(int, input().split()))
    if E == 0:
        print(0)
        return
    
    for i in range(E):
        _from, to, cost = list(map(int, input().split()))
        djk.add(_from, to, cost)

    d = djk.shortest_path(s)
    
    for cost in d:
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Runtime Error):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)
            # キューに格納されている最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                if not (v,i) in self.edges: continue

                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d


if __name__ == "__main__":
    djk = Dijkstra()
    V, E, s = list(map(int, input().split()))
    if E == 0:
        print(0)
        return
    
    for i in range(E):
        _from, to, cost = list(map(int, input().split()))
        djk.add(_from, to, cost)

    d = djk.shortest_path(s)
    
    for cost in d:
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Runtime Error):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self, V=None):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点数
                    - 頂点数が与えられたときは、すべての辺をINFで初期化する
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

        if V is not None:
            for u in range(V):
                for v in range(V):
                    self.edges[(u,v)] = float("INF")

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)
            # キューに格納されている最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                if not (v,i) in self.edges: continue

                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d


if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    djk = Dijkstra(V)
    """
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
    """
    for i in range(E):
        _from, to, cost = list(map(int, input().split()))
        djk.add(_from, to, cost)

    d = djk.shortest_path(s)
    
    for cost in d:
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Runtime Error):
class BellmanFord():
    """ ベルマンフォード法
    重み付き有向グラフにおける単一始点最短路アルゴリズム
    
    * 使用条件
        - DAG（有向グラフで閉路を持たない）であること
        - 負のコストがあってもOK
    
    * 負の閉路がある場合、最短路は求まらないが、負の閉路の検出はできる
    
    * 計算量はO(V*E)
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _from, _to, _cost):
            self.from_ = _from
            self.to = _to
            self.cost = _cost
        
    def __init__(self):
        self.edges = []  # 辺
        self.v_set = set()  # 頂点の集合
    
    @property
    def E(self):
        """ 辺数 """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges.append(self.Edge(_from, _to, _cost))
        self.v_set.add(_from)
        self.v_set.add(_to)
    
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        d = [float("inf")] * self.V
        d[s] = 0
    
        while True:
            do_update = False
            for i in range(self.E):
                e = self.edges[i]
                if d[e.from_] != float("inf") and d[e.to] > d[e.from_]+e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    do_update = True
            
            if not do_update: break
        
        return d
    
    def exist_negative_loop(self):
        """ 負の閉路が存在するか否か
        Returns:
            (bool): 負の閉路が存在する(True)/しない(False)
        """
        d = [0] * self.V
        for i in range(self.V):
            for j in range(self.E):
                e = self.edges[j]
                if d[e.to] > d[e.from_] + e.cost:
                    d[e.to] = d[e.from_] + e.cost
                    # n回目にも更新があるなら負の閉路が存在する
                    if i == self.V-1: return True
        return False
    
if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    bf = BellmanFord()
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            bf.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            bf.add(_from, to, cost)

    d = bf.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Time Limit Exceeded):
class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self, V=None):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点数
                    - 頂点数が与えられたときは、すべての辺をINFで初期化する
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

        if V is not None:
            for u in range(V):
                for v in range(V):
                    self.edges[(u,v)] = float("INF")

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)
            # キューに格納されている最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                if not (v,i) in self.edges: continue

                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d


if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    djk = Dijkstra()
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in djk.v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Time Limit Exceeded):
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self, V=None):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点数
                    - 頂点数が与えられたときは、すべての辺をINFで初期化する
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

        if V is not None:
            for u in range(V):
                for v in range(V):
                    self.edges[(u,v)] = float("INF")

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                
                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    djk = Dijkstra()
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in djk.v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Runtime Error):
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self, V=None):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点数
                    - 頂点数が与えられたときは、すべての辺をINFで初期化する
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

        if V is not None:
            for u in range(V):
                for v in range(V):
                    self.edges[(u,v)] = float("INF")

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                """
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                
                cost = self.edges[(v,i)]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in djk.v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Time Limit Exceeded):
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """        
    def __init__(self):
        """ 重み付き有向辺 
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点数
                    - 頂点数が与えられたときは、すべての辺をINFで初期化する
        """
        self.edges = {}  # edges[(u,v)] = cost := 辺(u,v)のコストcost
        self.v_set = set()  # 頂点の集合

    @property
    def E(self):
        """ 辺数 
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return len(self.edges)
    
    @property
    def V(self):
        """ 頂点数 """
        return len(self.v_set)
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.edges[(_from, _to)] = _cost
        self.v_set.add(_from)
        self.v_set.add(_to)
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(self.V):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                
                cost = self.edges.get((v,i), float("inf"))  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    djk = Dijkstra()
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in djk.v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)

Buggy python submission (verdict: Runtime Error):
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := uに隣接してるi番目の頂点
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                cost = self.G[v][i]  # vからiへのコスト
                if d[i] > d[v] + cost:
                    d[i] = d[v] + cost # dの更新
                    heapq.heappush(que, (d[i], i)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)



Fixed submission:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK
    
    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E
    
    @property
    def V(self):
        """ 頂点数 """
        return self._V
    
    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1
        
    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す 
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短路
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [float("inf")] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # (最短距離, 頂点の番号)をヒープに追加する

        while len(que) != 0:
            prov_cost, v = heapq.heappop(que)  # prov_cost := 暫定的な最短距離
            # キューに格納されている暫定的な最短距離が、現在計算できている最短距離より大きければ、dの更新をする必要はない
            if d[v] < prov_cost: continue

            # 他の頂点の探索
            for i in range(len(self.G[v])):
                """(1)遅い
                try:
                    self.edges[(v,i)]
                except KeyError:
                    continue
                """
                """ vからiへのコストは全探索せずに、存在するもののみ探したい """
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost # dの更新
                    heapq.heappush(que, (d[e.to], e.to)) # キューに新たな仮の距離の情報をpush
        return d

if __name__ == "__main__":
    V, E, s = list(map(int, input().split()))
    v_set = set()  # 頂点の集合
    djk = Dijkstra(V)
    if V == 1:
        print(0)
        exit()
        
    if E == 0:
        for i in range(V-1):
            djk.add(i, i+1, float("INF"))
    else:
        for i in range(E):
            _from, to, cost = list(map(int, input().split()))
            djk.add(_from, to, cost)
            v_set.add(_from)
            v_set.add(to)

        for i in range(V):
            # 入力に存在しない頂点があるとき、適当にINFの辺を作成する
            if not i in v_set:
                djk.add(i, 0, float("inf"))

    d = djk.shortest_path(s)
    
    for i in range(V):
        if i >= len(d):
            print("INF")
            continue

        cost = d[i]
        if cost == float("inf"):
            print("INF")
        else:
            print(cost)