Islands Survival

problem

There is a simple concatenated undirected graph with $N$ vertices and $M$ edges. The vertices are numbered $1, 2, \ dots, N$. The edges are numbered $1, 2, \ dots, M$, and the edge $i$ connects the vertices $a_i$ and $b_i$. Also, the edge $i$ disappears at time $t_i$. It takes a unit time to pass through each side. You are initially at vertex 1 at time 0. You want to maximize the score you get by time $T$ by acting optimally. The score is initially 0 and the event occurs according to:

1. If the current time $t'$ satisfies $t'\ geq T$, it ends. If not, go to 2.
2. All edges $i$ with $t_i = t'$ disappear.
3. If the vertex you are in is $v$ and the number of vertices contained in the connected component including the vertex $v$ is $x$, $x$ will be added to the score.
4. You either move to one of the vertices $v$ and adjacent to it, or stay at vertex $v$. However, in the former case, the edge that has already disappeared cannot be used.
5. As $t'\ gets t'+ 1$, go to 1.

Find the maximum score you can get.

output

Output the maximum score. Also, output a line break at the end.

Example

Input

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

Output

8

inputFormat

outputFormat

output

Output the maximum score. Also, output a line break at the end.

Example

Input

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

Output

8

样例

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

8