There are $$$n$$$ cities in Dadorlandtiria, and cities are connected with $$$m$$$ undirected roads. The $$$i$$$-th road connects cities $$$u[i]$$$ and $$$v[i]$$$. Cities are numbered from $$$0$$$ to $$$n-1$$$.
Unfortunately, all roads in Dadorlandtiria are too old. That is, after going through the $$$i$$$-th road, the road becomes impassable and needs $$$w[i]$$$ dadorian dollars to be repaired. After crossing, the repaired road becomes impassable again, and it needs another $$$w[i]$$$ dadorian dollars to be passable and so on. Initially, all roads are passable.
Let's say you want to travel from city $$$x$$$ to city $$$y$$$, and then return to city $$$x$$$. Let $$$f(x, y)$$$ be the minimum cost to repair the roads to make the travel possible.
Your task is to count the total number of pairs with $$$f(x, y) \le T$$$, where $$$0 \le x \lt y \le n-1$$$ and $$$T$$$ is a given integer.
The first line contains $$$n$$$, $$$m$$$, and $$$T$$$. ($$$2 \le n \le 2\cdot 10^5$$$, $$$n-1 \le m \le 2\cdot 10^5$$$, $$$0 \le T \le 2 \cdot 10^{14}$$$).
The next $$$m$$$ lines contain $$$u[i], v[i], w[i]$$$. ($$$0 \le u[i] \lt v[i] \le n-1$$$, $$$1 \le w[i] \le 10^9$$$).
It is guaranteed that there is at most one road between any pair of cities. Also, each pair of cities is reachable from each other using the given roads.
Print the number of pairs with $$$f(x, y) \le T$$$.
| Group | Add. constraints | Points |
| $$$0$$$ | examples | $$$0$$$ |
| $$$1$$$ | $$$n \le 200, m = n - 1$$$ | $$$6$$$ |
| $$$2$$$ | $$$n \le 2000, m = n - 1$$$ | $$$8$$$ |
| $$$3$$$ | $$$m=n-1$$$ | $$$27$$$ |
| $$$4$$$ | $$$T \le 100$$$ | $$$20$$$ |
| $$$5$$$ | $$$n \le 200$$$ | $$$11$$$ |
| $$$6$$$ | $$$n \le 2000$$$ | $$$12$$$ |
| $$$7$$$ | — | $$$16$$$ |
8 9 4 0 1 2 0 4 3 1 4 3 2 4 4 2 6 1 3 5 3 3 6 2 2 5 6 3 7 5
21
Let's calculate $$$f(0, 7)$$$.
You need to go through cities $$$0 \rightarrow 4 \rightarrow 2 \rightarrow 6 \rightarrow 3 \rightarrow 7$$$.
 |  |
To return to city $$$0$$$, you need to repair roads $$$(2, 4)$$$ and $$$(3, 7)$$$ for $$$4$$$ and $$$5$$$ dadorian dollars, respectively. So, $$$f(0, 7) = 9$$$.
The total number of pairs with $$$f(x, y) \le 4$$$ equals $$$21$$$.
