题目描述

在一张带权无向图中，求指定两点的最短距离。

若图中存在一个环，且环上各边权值之和为负数，则称此环为负环。

如果不能到达或者存在负环则输出"No"。

输入格式

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

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

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

输出格式

一个整数，代表从s到t的最短距离。如果存在负环则输出"No"。

输入/输出样例

5 6
1 5
1 2 4
2 3 3
1 4 1
2 4 2
4 5 4
2 5 1

4

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

No

说明/提示

时间1000ms，内存256MiB