题目描述

小青需要从城市A到城市B，途中可以经过多个城市。每个城市之间都有一条道路，每条道路都有一个花费。小青想知道从城市A到城市B的最小花费是多少。

输入格式

输入第一行是两个整数n和m，表示城市的数量和道路的数量。 接下来的m行，每行包含三个整数u、v和w，表示城市u和城市v之间有一条花费为w的道路。 最后一行是两个整数s和t，表示小青的出发城市和目标城市。

输出格式

输出一个整数，表示从城市s到城市t的最小花费。如果无法到达，输出-1。

样例

样例 1

输入 # 1

3 3
1 2 10
2 3 5
1 3 20
1 3

输出 # 1

15