带权最短路 · 008

题目描述

求非负权有向图中从 1 到 $n$ 的最短距离，不可达输出 -1。

这是“经典赛事”题库的第 8 题。

输入格式

第一行 $n,m$；随后 $m$ 行为 $u,v,w$。

输出格式

输出最短距离或 -1。

样例输入

5 7
1 2 10
2 3 14
3 4 5
4 5 20
5 1 97
3 2 31
3 4 12

样例输出

49

限制

• 时间限制：2 秒
• 内存限制：256 MiB

来源与授权

• 题目与数据： 智链细米 IT 社区原创训练变体（dijkstra-0051）。
• 知识路线参考： AlgoNote @ 2aa4fd0a2214；代码随想录 @ b43def349578。
• 引用说明： 代码随想录作者为程序员 Carl；本题没有复制 LeetCode 或第三方竞赛题面、样例、题解与测试数据。
• 授权记录： organizer-confirmed-2026-08-07。
• 主办方： 智链细米 IT 社区；设备支持： EaglesLab。