代码随想录算法训练营day59| 47.参加科学大会 94.城市间货物运输

# dijkstra算法-最小堆；适用于稀疏图，边少，从边出发；邻接表
import heapq

class Edge:
    def __init__(self, to, val):
        """用于定义邻接表，键值对，键是起始节点，值是（指向的节点，边的权值）"""
        self.to = to   # 指向的节点
        self.val = val  # 边的权值

def dijkstra(n, m, edges, start, end):
    grid = [[] for _ in range(n+1)]  # 邻接表
    for p1,p2,val in edges:
        grid[p1].append(Edge(p2, val))
    minDist = [float('inf')] * (n+1)
    visited = [False]*(n+1)
    
    pq = []
    heapq.heappush(pq, (0, start))
    minDist[start] = 0
    
    while pq:
        cur_dist, cur_node = heapq.heappop(pq)
        if visited[cur_node]:
            continue
        visited[cur_node] = True
        
        for edge in grid[cur_node]:
            if not visited[edge.to] and cur_dist+edge.val < minDist[edge.to]:
                minDist[edge.to] = cur_dist+edge.val
                heapq.heappush(pq, (minDist[edge.to], edge.to))
    return -1 if minDist[end]==float('inf') else minDist[end]

# 输入值
n, m = map(int, input().split())
edges = []
for i in range(m):
    edges.append(list(map(int, input().split())))
    start = 1
    end = n
# 输出结果
result = dijkstra(n, m, edges, start, end)
print(result)




# # dijkstra算法，类似于prim
# # 统计每个节点到源点的最小距离（minDist），和是否被访问过(visited)
# # 找到距离源点最近的未访问过的节点，选中它；将它标记为访问过；更新minDist

# def dijkstra(n, m, start, end):
#     # 初始化邻接矩阵，每个节点到源点的距离都设置为无穷大，因为后面要保存最短距离
#     grid = [[float('inf')]*(n+1) for _ in range(n+1)]
#     for p1, p2, val in edges:
#         grid[p1][p2] = val
    
#     # 初始化距离数组，都为无穷大
#     minDist = [float('inf')]*(n+1)
#     minDist[start]=0  # 自己到自己的距离为0
#     # 访问数组，初始为未访问
#     visited = [False]*(n+1)
    
#     # 遍历所有节点
#     for _ in range(1, n+1):
#         minVal = float('inf')
#         cur = -1
        
#         # 选择距离源点最近且未访问过的节点
#         for v in range(1, n+1):
#             if not visited[v] and minDist[v]<minVal:
#                 minVal = minDist[v]
#                 cur = v
#         # 若节点都访问过，则提前结束
#         if cur == -1:
#             break
#         # 标记该节点为被访问
#         visited[cur] = True
        
#         # 更新剩余未访问节点到源点的距离 ？？？？？ 真没看懂啊！！！！！
#         for v in range(1, n+1):
#             if not visited[v] and grid[cur][v] != float('inf') and minDist[cur]+grid[cur][v]<minDist[v]:
#                 minDist[v] = minDist[cur]+grid[cur][v]
#     return -1 if minDist[end]==float('inf') else minDist[end]
    
# # 输入值
# n, m = map(int, input().split())
# edges = []
# for _ in range(m):
#     edges.append(list(map(int, input().split())))
# start = 1
# end = n
# result = dijkstra(n, m, start, end)
# print(result)