Given a bidirectional graph G=(V,E) with n vertices and m edges, it’s easy to find the shortest path between vertex S and T. Your task is to delete a set of edges with minimum cost, such that the shortest path in new graph is longer than the original one.

The first line of each test case contains two integers n and m, which specify the number of vertices and edges. (2 ≤ n ≤ 1000, 1 ≤ m ≤ 10000). The second line consists of two integer S and T, indicating the source and the sink. (1 ≤ S,T ≤ n, S ≠ T) The next m lines each contains four integers u_i, v_i, w_i and c_i, indicating that there’s an edge between vertex u_i and v_i with length w_i, and the cost of deleting it is c_i. (1 ≤ u_i,v_i ≤ n, 0 ≤ w_i,c_i ≤ 1000)

A test case with n=m=0 indicates the end of input.

It is guaranteed that shortest path in initial graph always exists, and length of the shortest path between S and T is regarded as infinity if they are not connected.

2 3
1 2
1 2 2 3
1 2 2 4
1 2 3 5
4 5
1 4
1 2 1 1
2 3 1 1
3 4 1 1
1 4 3 2
2 2 2 3
4 5
2 3
1 2 3 2
2 4 3 4
1 3 2 3
3 4 2 3
1 4 0 1
0 0

Case 1: 7
Case 2: 3
Case 3: 6