Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2526
FatMouse and JavaBean II

Time Limit: 2 Seconds      Memory Limit: 65536 KB

So this is the second version of FatMouse and his favorite food, JavaBean -- boy he just cannot have enough of it, can he? Again FatMouse was lucky enough to find a map of another storehouse which contains JavaBean. The map showed several scattered rooms storing JavaBeans and the rooms were connected by some tunnels. Amount of JavaBeans in each room and the length of each tunnel between any pair of rooms were marked on the map. After some negotiations FatMouse finally had a cat agree to clear two of the rooms' guards for him to enter and leave, under the condition that he had to leave as soon as possible from the other end. Now he comes to you with his map, asking if you could tell him the path for getting the maximum amount of JavaBeans.

Input:

Input consists of several test cases.
For each test case, the first line contains 4 positive integers: N (<= 500) - the number of rooms (and the rooms are numbered from 0 to N-1), M - the number of tunnels, Rm1 and Rm2 - the rooms that FatMouse may enter or leave. The next line contains N integers, where the i-th integer is the number of JavaBeans at the i-th room. Then M lines follow, each describes a tunnel with three integers R1, R2 and L, which are the pair of rooms connected by a tunnel and the length of that tunnel, respectively.
It is guaranteed that there exists at least one path from Rm1 to Rm2.

Output:

For each test case, print in the first line two numbers: the number of different paths that satisfy his agreetment with the cat, and the maximum amount of JavaBeans FatMouse can possibly take. Then in the second line, print the rooms on the path which bring him the maximum profit, from Rm1 to Rm2. It is guaranteed that this path is unique since I am too lazy to write up a special judge program :)
All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
1 0 0 0
2
Sample Output:
2 4
0 1 2
1 2
0


Author: CHEN, Yue
Source: ZOJ Monthly, September 2005
Submit    Status