该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

  给定 $n$ 个点（$1 ∼ n$ 表示），$m$ 条边构成的无向连通图（任意两点互相可达）。

  第 $i$ 条边 $edges[i] = \{x, y, z\}$ 表示 $x$ 与 $y$ 之间有一条长度为 $z$ 的无向边。请你求出从 $1$ 号点到 $n$ 号点的最短路距离。

注：请使用 Dijkstra 算法求解

  数据范围：100%的数据满足：$1\leq n \leq 10^3, 1\leq m \leq 10^5, 1\leq z\leq 10^9$

Format

  你的提交代码格式如下所示

#include "Solution.h"

long long Solution::shortest_path(int n, vector<vector<int>>& edges) {
    // 请在这里完成你的代码

}

Samples

  你的程序 不需要输入输出，提供样例用于自测

4 6
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

3