CF20C.Dijkstra?

You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between the vertex 1 and the vertex n.

给你一个带权无向图。顶点编号从 $1$ 到 $n$。你的任务是求出顶点 $1$ 与顶点 $n$ 之间的最短路径。

The first line contains two integers n and m (2 ≤ n ≤ 105, 0 ≤ m ≤ 105), where n is the number of vertices and m is the number of edges. Following m lines contain one edge each in form a__i, b__i and w__i (1 ≤ a__i, b__i ≤ n, 1 ≤ w__i ≤ 106), where a__i, b__i are edge endpoints and w__i is the length of the edge.

It is possible that the graph has loops and multiple edges between pair of vertices.

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$0 \leq m \leq 10^5$），其中 $n$ 表示顶点数，$m$ 表示边数。接下来的 $m$ 行每行描述一条边，格式为 $a_i$, $b_i$ 和 $w_i$（$1 \leq a_i, b_i \leq n$，$1 \leq w_i \leq 10^6$），其中 $a_i$、$b_i$ 是该边的两个端点，$w_i$ 是该边的长度。

图中可能存在自环以及任意一对顶点之间的多条边。

Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.

若不存在路径，仅输出整数 $-1$；否则输出最短路径。若存在多个解，输出其中任意一个即可。