Airline ticket#6305
An airline is running a unique promotion where it offers passes with the following rules:
Each flight operated by the airline has a specific value in conditional units.
The pass has a certain value, also measured in these conditional units.
After each flight, the cost of that flight, in conditional units, is deducted from the pass.
Each subsequent flight must begin in the city where the previous flight ended.
If the remaining conditional units on the pass are insufficient for the next flight, they are forfeited.
Given the pass's value and the costs of all flights, determine if it's possible to plan the flights such that the pass is fully utilized, with no conditional units left over.
The first line contains three natural numbers separated by spaces:
(1 \leq n \leq 1000) – the number of cities served by the airline, (1 \leq m \leq 1000) – the number of flights available, (1 \leq v \leq 1000) – the value of the pass.
Each of the next lines describes the cost of a flight. The first two numbers, v_1 and v_2 (1 \leq v_1, v_2 \leq n), represent the cities connected by the flight, and the third number, (1 \leq w \leq 1000), is the cost of the flight from city v_1 to city v_2 (v_1 and v_2 are different). The numbers are separated by spaces.
It is guaranteed that there is no more than one direct flight between any two cities in each direction.
Print YES if it is possible to plan the flights such that the pass is completely used up, otherwise print NO.
Example 1