【模板】单源最短路2
题号：NC226498
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给你一个无向图，图中包含 5000 个点 m 个边，任意两个点之间的距离是 w ，无重边或自环。请求出1号点到n号点的最短距离。

注意：图中可能存在孤立点，即存在点与任意点都没有边相连

如果1号点不能到达n号点，输出-1.


输入描述:


第一行两个整数n和m，表示图的点和边数。





接下来m行，每行三个整数u，v, w，表示u到v有一条无向边, 长度为w。

输出描述:





输出一行，表示1到n的最短路，如不存在，输出-1.
示例1

输入

复制 
4 4
1 2 3
2 4 7
3 4 5
3 1 3

输出

复制 
8
示例2

输入

复制 
4 3
1 2 5
2 3 3
3 1 3

输出

复制 
-1

说明

1号点不能到4号点。