# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

By reborn · Limits 1s, 256 MB Ada is wondering in her dreamland. Her dreamland consists of $n$ spots. She has this weird machine with her that shows real numbers. And whenever she goes from spot $u$ to $v$, if she can (by following a trail), the value shown in the machine gets multiplied with $c_{uv}$ which is another weird value for each trail that exists between two spots.

Ada is currently in spot 1 and her machine currently reads value $d$. She wants to go to spot $n$ in a way so that the machine shows zero when she reaches $n$. Is that possible?

Please note that, Ada can visit a spot multiple times if it helps her.

(Change from printed statement) Ada’s machine displays zero when the value is either zero or tends to be zero. To say that $x$ tends to zero is to say that $x$ varies in such a way that its numerical value becomes and remains less than any positive number that we may choose, no matter how small.

## Input

First line contains two integers and one positive real number $n, ~m, ~d$; the number of spots, the number of trails, the initial reading of the machine respectively.

Each of the next $m$ lines contains two integers $u, ~v$ and a positive real number $c_{uv}$; which corresponds to a trail from spot $u$ to spot $v$ with the multiplier $c_{uv}$.

$c_{uv}$ and $d$ will have exactly 2 digits after the decimal place.

Note that the trails are unidirectional. Also there will be no trail from a spot to itself. And there exists at most one trail from a spot $u$ to $v$.

### Constraints

• $2 \leq n \leq 10^3$.
• $0 \leq m \leq \min (10^5, n(n-1))$.
• $1 \leq u, v \leq n$.
• $0 < c_{uv}, d \leq 10^6$.

## Output

If Ada can not reach spot $n$ anyhow, please output “Unreachable” on a line.
Else, print “Yes” if she can obtain zero at the machine reading after arriving in spot $n$. Print “No” otherwise.

## Sample

InputOutput
5 5 1.00
1 2 0.10
2 3 7.00
2 4 2.00
4 3 0.90
3 5 0.05

No There are two ways to go to 5 from 1:
A. 1-2-3-5 yields a value of 1 x 0.10 x 7.00 x 0.05 = 0.035.
B. 1-2-4-3-5 yields a value of 1 x 0.10 x 2.00 x 0.90 x 0.05 = 0.09.

None of them yields 0.

Discussion
Statistics

27% Solution Ratio

NirjhorEarliest, 2w ago

EgorKulikovFastest, 0.2s

NirjhorLightest, 4.1 MB

tmwilliamlin168Shortest, 1142B

Submit