题目描述

假如有下图所示的交通示意图，有向边上的数值表示边的长度，求A到D的最短路径的长度 。

输入格式

第一行2个整数n和m，n表示有多少个顶点，m表示边的总数。

第2到第m+1行每行3个整数，表示一条边的起点编号、终点编号和长度。

输出格式

一个整数，表示从1到n的最短路径长度。如果不能到达输出-1

输入输出样例

4 4
1 2 13
1 3 19
2 4 28
3 4 15

34

说明/提示

对于 100% 的数据，1≤n,m≤100。