Untitled

import heapq

class Solution(object):

    def shortestPath(self, n, m, edges):

        adj = [[] for _ in xrange(n + 1)]

        for it in edges:
            adj[it[0]].append((it[1], it[2]))
            adj[it[1]].append((it[0], it[2]))

        pq = []

        dist = [float('inf')] * (n + 1)
        parent = range(n + 1)

        dist[1] = 0

        heapq.heappush(pq, (0, 1))

        while pq:

            dis, node = heapq.heappop(pq)

            for adjNode, edW in adj[node]:

                if dis + edW < dist[adjNode]:
                    dist[adjNode] = dis + edW
                    heapq.heappush(pq, (dis + edW, adjNode))
                    parent[adjNode] = node

        if dist[n] == float('inf'):
            return [-1]

        path = []
        node = n

        while parent[node] != node:
            path.append(node)
            node = parent[node]

        path.append(1)

        return path[::-1]


if __name__ == "__main__":
    V = 5
    E = 6

    edges = [[1, 2, 2], [2, 5, 5], [2, 3, 4], [1, 4, 1], [4, 3, 3], [3, 5, 1]]

    obj = Solution()
    path = obj.shortestPath(V, E, edges)

    for i in xrange(len(path)):
        print path[i],
    print