曾大美送快递

内存限制: 128M   时间限制: 1S

题目描述


输入

输出

样例输入

6 3 3 4 
1 2 5 
3 4 5 
5 6 10 
3 5 -100 
4 6 -100 
1 3 -10 

样例输出

NO PATH 
NO PATH 
5 
0 
-95 
-100