Farmer John����һ���µ��������������ţ�����۷������е��顣�����ţ���͵�T������ (1 <= T <= 25,000)�����Ϊ1�T����Щ����֮��ͨ��R����· (1 <= R <= 50,000�����Ϊ1��R) ��P������ (1 <= P <= 50,000�����Ϊ1��P) ���ӡ�ÿ����·i���ߺ���i���ӳ���A_i (1 <= A_i <= T)��B_i (1 <= B_i <= T)������ΪC_i�����ڵ�·��0 <= C_i <= 10,000;Ȼ�����ߵĻ��Ѻ����棬����C_i�����Ǹ���(-10,000 <= C_i <= 10,000)����·��˫��ģ����Դ�A_i��B_i��Ҳ���Դ�B_i��A_i�����Ѷ���C_i��Ȼ��������֮��ͬ��ֻ���Դ�A_i��B_i����ʵ�ϣ���������ֲ�����̫���ţ�Ϊ������г����̨ ��һЩ���߱�֤�������һ�����߿��Դ�A_i��B_i����ô��֤������ͨ��һЩ��·�ͺ��ߴ�B_i�ص�A_i������FJ����ţ���繫��ʮ�ָ���������Ҫ������ţ��ÿһ�����������ҵ��ӷ������ij���S(1 <= S <= T) ����ţ�͵�ÿ�����������˵ķ���������֪�����Dz����ܵġ�

* 第1行：四个空格隔开的整数: T, R, P, and S * 第2到R+1行：三个空格隔开的整数（表示一条道路）：A_i, B_i 和 C_i * 第R+2到R+P+1行：三个空格隔开的整数（表示一条航线）：A_i, B_i 和 C_i

* 第1到T行：从S到达城镇i的最小花费，如果不存在输出"NO PATH"。

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

USACO 2011 January 金组