Shortest Distance in a Town

You are given a town with N houses numbered from 1 to N and M roads connecting these houses. Each road is described by four integers: a, b, l, and d.

The value a and b denote the houses connected by the road, l is the length of the road, and d indicates the road's direction. Specifically, if d = 1, the road is bidirectional (i.e. travel is allowed in both directions); if d = 0, it is one-way from house a to house b.

Your task is to compute the shortest distance from a given starting house to a destination house. If there is no path between the two, output unreachable.

Recall that the shortest path from house s to house t minimizes the sum of the lengths of the roads used. In mathematical notation, if the distance to reach house i is denoted by \(d(i)\), then

\[ d(t) = \min_{\text{path } s \to t} \sum_{\text{edge } e \in \text{path}} l(e) \]

If no such path exists, we consider \(d(t) = \infty\) and output unreachable.

inputFormat

The input is given via stdin and has the following format:

N M s t
a1 b1 l1 d1
a2 b2 l2 d2
... (M lines in total)

Where:

• N is the number of houses.
• M is the number of roads.
• s is the starting house and t is the destination house.
• Each road is represented by four integers: a, b, l, and d.

All values are separated by spaces or newlines.

outputFormat

The output should be printed to stdout. It is a single line containing either the shortest distance (an integer) from s to t or the string unreachable if no such route exists.

## sample

4 4 1 4
1 2 5 1
2 3 10 0
3 4 2 1
1 3 15 0

17