题目描述

给出一个有向图，所有边的权值均为正数。请判断图中是否存在一个从某个点出发并最终回到该点的路径（即回路），并且该路径的总长度严格小于 K。

格式

输入

第一行包含三个整数 n, m, K（1≤n≤100，1≤m≤10000，1≤K≤10^9）。 接下来 m 行，每行包含三个整数 u, v, w，表示从 u 到 v 存在一条边权为 w 的有向边（1≤u,v≤n，1≤w≤100）。

注意：路径允许经过重复的点和边；要求存在某个起点 s，使得从 s 出发经过若干条边后回到 s，且该回路的总长度严格小于 K。

输出

如果存在满足条件的回路，输出 YES，否则输出 NO。

样例

3 3 5
1 2 2
2 3 1
3 1 1

YES