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

NEERC, Central subregion, Rybinsk, October 2002

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. 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.

Input

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.

Output

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.

Samples

inputoutput
3 2 20
1 2 10
2 3 5
NO
3 3 1000
1 2 1
2 3 1
1 3 1
YES
Problem Source: 2002-2003 ACM Central Region of Russia Quarterfinal Programming Contest, Rybinsk, October 2002
To submit the solution for this problem go to the Problem set: 1227. Rally Championship