ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1227. Rally Championship

Time limit: 1.0 second
Memory limit: 64 MB
A high-level international rally championship is about to be held. The rules of the race state that the race is held on ordinary roads and the route has a fixed length. You are given a map of the cities and two-way roads connecting it. To make the race safer it is held on one-way roads. The race may start and finish anyplace on the road. Determine if it is possible to make a route having a given length S.


The first line of the input contains integers M, N and S that are the number of cities, the number of roads the length of the route (1 ≤ M ≤ 100; 1 ≤ N ≤ 10 000; 1 ≤ S ≤ 2 · 106).
The following N lines describe the roads as triples of integers: P, Q, R. Here P and Q are cities connected with a road, and R is the length of this road. All numbers satisfy the following restrictions: 1 ≤ P, QM; 1 ≤ R ≤ 32000.


Write YES to the output if it is possible to make a required route and NO otherwise. Note that answer must be written in capital Latin letters.


3 2 20
1 2 10
2 3 5
3 3 1000
1 2 1
2 3 1
1 3 1
Problem Source: 2002-2003 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 2002