Description

三周前还在切网线的杰哥如今金盆洗手办起了招待所，热心接待那些翘家的人。杰哥的招待所又大又现代化，一共有n个房间（房间编号为1,...,n），房间之间共有m条用于运送物资的单向传送带，每条传送带有单位时间运输容量c。一天一名叫阿伟的少年预定了杰哥招待所的t号房间，准备已久的杰哥早就在教超商店购买了足量的面包，并放置在s(s≠t)号房间。为了更好地招待阿伟，杰哥希望能运送尽可能多的面包到他所住的房间。但由于杰哥还要忙着做CPU，所以他希望问题求解能力超勇的你能帮他解决这个问题。

Format

Input

第一行包含四个正整数n，m，s，t，分别表示房间数量，传送带数量，放置面包的房间号和阿伟的房间号。
接下来m行，每行3个整数a，b，c，表示这一条传送带从a号房间运送物品至b号房间，其单位时间运输容量为c。
1≤n≤200
1≤m≤1000
1≤c≤100
1≤s,t≤n

Output

一个整数，代表单位时间内可以运送到阿伟房间的最大面包数量。

Sample 1

Input

4 4 1 4
1 2 1
1 3 1
2 4 1
3 4 1

Output

2

Limitation

2s, 128MB for each test case.

Hint

杰哥投资招待所非常康慨，所以从一个房间到另一个房间可能有不止一条传送带。