Minimum Additional Connections

You are given a network of n servers (nodes) connected by m bidirectional links (edges). Each link between two servers has an associated latency (or weight) l. Your task is to determine whether the current network allows every server to communicate with every other server with a maximum latency not exceeding a given threshold k. In other words, for every pair of nodes i and j the condition

[ d(i,j) \le k ]

must hold, where d(i,j) represents the shortest latency path between node i and node j. If there exists any pair of nodes for which the shortest latency exceeds k, then it is impossible to achieve the required performance even if additional connections were to be added. For this problem, output 0 if the current network already satisfies the latency requirement and -1 if it does not.

inputFormat

The input is read from standard input (stdin) with the following format:

 n m k
 u1 v1 l1
 u2 v2 l2
 ...
 um vm lm

Here, n is the number of nodes, m is the number of edges, and k is the maximum allowed latency. Each of the next m lines contains three integers u, v, and l representing an edge between nodes u and v with latency l.

outputFormat

Output a single integer to standard output (stdout):

• Output 0 if every pair of nodes is connected with a latency at most k.
• Output -1 otherwise.

6 7 4
1 2 2
2 3 2
3 4 2
4 5 2
5 6 2
1 5 7
2 6 1

-1