No submission language available for this problem.

Background

Special for beginners, ^_^

Description

这将是一道单源最短路训练题，请看清题意。

你将获得一张图 $G(n, m)$ 表示 $n$ 个顶点 $m$ 条单向边，每条边都有一个权值，注意权值可能为负值。

你需要计算出，在这张图中，起点 $s$ 到达终点 $t$ 的最小权值和。

你可能面临几种情况：

• 若存在负环，则输出 Negative Ring
• 若起点 $s$ 无法到达终点 $t$，则输出 INF
• 若起点 $s$ 能够到达终点 $t$，则输出最小权值和的值

Format

Input

第一行 4 个整数 $n, m, s, t$，其含义如题所描述。

第二行开始的 $m$ 行，每行 3 个整数 u，v，w 表示一条起点 u，终点 v，权值为 w 的边。

Output

一行一个按要求的输出。

Samples

5 5 1 5
1 2 5
1 3 7
3 5 1 
1 4 10 
4 5 -4

6

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

Negative Ring

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

INF

Limitation

$1 <= n <= 10000$;

$0 <= m <= min(n * (n - 1), 20000)$;

$|w| <= 20$

1s, 1024KiB for each test case.