题解 | #【模板】单源最短路2#

# bfs

import math

class Solution:

    def slove(self, n: int, m: int, links: List[List[int]]) -> int:
        if n == 1:
            return 0

        linkmap = dict()
        steplist = dict()
        for link in links:
            s = link[0]
            e = link[1]
            w = link[2]
            if s == e:
                continue

            if s not in linkmap:
                linkmap[s] = dict()
            if e not in linkmap:
                linkmap[e] = dict()
            linkmap[s][e] = w
            linkmap[e][s] = w
            steplist[s] = float(math.inf)
            steplist[e] = float(math.inf)

        nextstack = set()
        stack = set()
        stack.add(1)
        steplist[1] = 0
        while len(stack) > 0:
            while len(stack) > 0:
                node = stack.pop()
                if node not in linkmap.keys():
                    continue

                minw = steplist[node]
                for tnode in linkmap[node].keys():
                    weight = linkmap[node][tnode]
                    if minw + weight >= steplist[tnode]:
                        continue
                    else:
                        steplist[tnode] = min(steplist[tnode], minw + weight)
                        nextstack.add(tnode)

            for node in nextstack:
                stack.add(node)
            nextstack.clear()
        
        if n in steplist and steplist[n] < math.inf:
            return steplist[n]
        else:
            return -1


if __name__ == '__main__':
    message = input()
    messagesplt = message.split(" ")
    n = int(messagesplt[0])
    m = int(messagesplt[1])

    link = []
    for _ in range(m):
        message = input()
        messagesplt = message.split(" ")
        link.append([int(messagesplt[0]), int(messagesplt[1]), int(messagesplt[2])])
    
    solution = Solution()
    result = solution.slove(n, m, link)
    print(result)