- Prepare
- Algorithms
- Graph Theory
- Minimum Penalty Path

# Minimum Penalty Path

# Minimum Penalty Path

Consider an undirected graph containing nodes and edges. Each edge has an integer *cost*, , associated with it.

The *penalty* of a path is the *bitwise OR* of every edge cost in the path between a pair of nodes, and . In other words, if a path contains edges , then the penalty for this path is **OR** **OR** ... **OR** .

Given a graph and two nodes, and , find the path between and having the *minimal possible penalty* and print its penalty; if no such path exists, print to indicate that there is no path from to .

**Note:** Loops and multiple edges are allowed. The bitwise OR operation is known as **or** in Pascal and as **|** in C++ and Java.

**Input Format**

The first line contains two space-separated integers, (the number of nodes) and (the number of edges), respectively.

Each line of the subsequent lines contains three space-separated integers , , and , respectively, describing edge connecting the nodes and and its associated penalty ().

The last line contains two space-separated integers, (the starting node) and (the ending node), respectively.

**Constraints**

**Output Format**

Print the minimal penalty for the optimal path from node to node ; if no path exists from node to node , print .

**Sample Input**

```
3 4
1 2 1
1 2 1000
2 3 3
1 3 100
1 3
```

**Sample Output**

```
3
```

**Explanation**

The optimal path is .

and .

The penalty for this path is: **OR** , so we print .