와우 네트워크

축제가 한창인 홍익대학교에서 학생회 소속의 네트워크 관리자 홍익이는 축제 기간 동안 캠퍼스 곳곳에 설치된 $N$개의 행사 부스를 관리합니다. 각 부스는 1번부터 $N$번까지의 번호를 가집니다.

원활한 행사 진행을 위해, 홍익이는 $M$개의 임시 무선 라우터를 대여했습니다. 각 라우터는 특정 두 부스를 지정된 시간 동안만 연결할 수 있습니다. 예를 들어, $i$번째 라우터는 $u\_i$번 부스와 $v\_i$번 부스를 축제 시작 후 $s\_i$초부터 축제가 끝나는 $T$초까지 계속 연결합니다.

홍익이는 전체 네트워크의 안정성을 실시간으로 파악하기 위해 불안정 점수를 도입했습니다. 특정 시각 $t$에서의 불안정 점수는, 해당 시각에 서로 연결된 부스들의 묶음의 개수, 즉 연결 요소(Connected Components)의 개수로 정의됩니다. 불안정 점수가 높을수록 네트워크가 여러 묶음으로 나뉘어 불안정하게 됩니다.

홍익이는 1부터 $T$까지의 각 정수 시각 $t$에 대한 불안정 점수를 모두 더한 총합을 계산하여 축제 기간 동안 네트워크의 안정성을 체크하려고 합니다. 바쁜 홍익이를 도와 네트워크 안정성을 대신 측정해 주세요!

첫째 줄에 부스의 수 $N$, 임시 라우터의 수 $M$, 축제 기간 $T$가 공백으로 구분되어 주어집니다. ($2 \le N \le 100\ 000,\ 1 \le M \le 100\ 000,\ 2 \le T \le 10^9$)

다음 $M$개의 줄에 걸쳐 각 라우터의 정보 $u, v, s$가 주어집니다. 이는 $u$번 부스와 $v$번 부스가 $s$초부터 $T$초까지 연결됨을 의미합니다. ($1 \le u, v \le N,\ u \ne v,\ 1 \le s < T$)

1부터 $T$까지의 각 정수 시각 $t$에 대한 불안정 점수의 총합을 출력합니다.