Problem1006--【2012四川省热身赛】Problem C. OR Shortest Path

1006: 【2012四川省热身赛】Problem C. OR Shortest Path

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 2  Solved: 1
[Submit] [Status] [Web Board] [Creator:]

Description

OR is a kind of bitwise operator, we deﬁned that as follow: for two number A and B in binar notation, let C = A OR B. Then for each bit of C, we can get its value by check the digit of corresponding position in A and B. For each digit, 1 OR 1 = 1, 1 OR 0 = 1, 0 OR 1 = 1, 0 OR 0 = 0. And we simply write this operator as |, like 2 | 1 = 3, 2 | 3 = 3.In bitland there is a strange method to calculate the length of a path using OR. If there are M
edges in a path, and the length of them are l1; l2; · · · ; lM, then the length of this path is l1 | l | · · · | lM. Now give you a undirected graph with N nodes and M edges, ﬁnd the OR shortes path between S and T. If S and T are disconnect, we consider the length between them is −1.

Input

First line of the input is a single integer T(T ≤ 30), indicates there are T test cases.
For each test case, the ﬁrst line is four integers N(2 ≤ N ≤ 104), M(1 ≤ M ≤ 105), S,T(1 ≤ S; T ≤ N; S ̸= T), indicates the number of nodes, the number of egdes, the startingnode and the target node respectively. Following M lines, each line contains three integers a bc(1 ≤ a; b ≤ N, a ̸= b, 0 ≤ c < 230), means there exist an undirected edge between node a and node b, and the length is c.

Output

For each test case, output one line. First ,output “Case #t: ”, where t is the number of test case,
from 1 to T. Then, you should output a single line contains a single number means the length of
the OR shortest path between S and T or −1.

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

Case #1: 3
Case #2: 6
Case #3: -1