QOJ.ac

QOJ

Time Limit: 0.5 s Memory Limit: 64 MB Total points: 100
[+5]

# 603. 单源最短路径

Statistics

Source: Libre OJ 119

给一个 n(1n2500) 个点 m(1m6200) 条边的无向图,求 st 的最短路。

Input

第一行四个由空格隔开的整数 nmst

之后的 m 行,每行三个正整数 sitiwi(1wi109),表示一条从 siti 长度为 wi 的边。

Output

一个整数表示从 st 的最短路长度。数据保证至少存在一条道路。

Example

Input

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

Output

7