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, Q ≤ M; 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