描述
Long long ago, there lived a lot of rabbits in the forest. Every rabbit lived in his own house and only meet each other in festival.
Let us consider the whole traffic network in the rabbit kingdom as a graph while the houses are nodes and the roads connected two houses are edges.
The festival would last for K days. For traffic congestion controlling reason, the i-th road would be closed on the Ci-th day (i.e. the rabbit cannot go through this road on the Ci-th day).
Now the rabbits want to calculate that how many pairs of rabbits are able to meet each other on the i-th day. Note that there lived exactly one rabbit in each house and two rabbits can meet each other if and only if there is a route between their houses which only consists non-closed road on that day.
输入
The input consists of at most 10 cases.
For each test case, the first line contains three integers N, M, K, which respectively indicate the number of houses, the number of roads and the number of days that the festival will last.
The next M lines describe this graph. For the i-th line, it contains three integer Xi, Yi, Ci, where Xi, Yi indicate the numbers of houses that the i-th road connect and Ci indicates the road would be close at the Ci-th day.
Houses are numbered from 1 to N. Roads are undirected and numbered from 1 to M. Days are numbered from 1 to K. 0 ≤ N, K ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ Xi, Yi ≤ N, Ci is positive. If Ci exceeds K, then this road will keep open during the whole festival.
输出
For each test case, output K lines. The i-th line contains only one integer indicating the number of rabbit pairs which are able to meet each other on the i-th day.
样例输入
7 8 4
1 2 4
1 3 3
3 4 2
3 6 2
5 3 1
4 5 1
5 6 1
7 6 3
样例输出
15
21
7
15