题目描述

游乐场的各区域之间都有路相连，已知相邻两个游乐区域的距离。求指定两个场所的最短距离。

输入格式

第一行为整数n、m(1≤n, m≤100)，表示图中点的个数和边的个数；

第二行为整数s、t(1≤s, t≤n)，表示起点和终点的数字；

此后的m行，每行描述一条边，由三个不超过100的整数u，v和w组成，表示顶点u到v之间有一条长度为w的边。

输出格式

一个整数，代表从s到t的最短距离。若不能到达输出-1。

输入/输出样例

7 12
1 5
1 2 3
1 3 6
1 4 2
2 3 1
3 4 3
2 5 7
3 5 8
3 6 4
3 7 2
5 6 2
4 7 12
6 7 1

9

说明/提示

时间1000ms，内存256MiB