K분 그래프

무방향 가중치 그래프가 $K$분 그래프라는 것은, 그래프의 모든 닫힌 보행 $P$에 대해 $P$의 간선 가중치 합이 항상 $K$의 배수라는 뜻이다. 한 간선을 여러 번 사용했다면 그 가중치도 사용한 횟수만큼 합에 더한다.

무방향 가중치 그래프 $G$와 양의 정수 $K$가 주어졌을 때, $G$가 $K$분 그래프인지 판별한다.

첫째 줄에 정점 개수 $N$, 간선 개수 $M$, 양의 정수 $K$가 공백으로 구분되어 주어진다. ($1 \le N \le 300\,000$, $0 \le M \le 500\,000$, $1 \le K \le 10^9$)

이후 $M$개의 줄에 정수 $v_i$, $w_i$, $x_i$가 공백으로 구분되어 주어진다. 이는 $v_i$번 정점과 $w_i$번 정점을 잇는 가중치 $x_i$의 양방향 간선을 뜻한다. ($1 \le v_i, w_i \le N$, $0 \le x_i \le 10^9$)

두 정점을 잇는 간선이 여러 개일 수 있으며, 같은 정점을 잇는 간선이 존재할 수 있다. 주어지는 그래프가 연결되어 있지 않을 수도 있다.

주어진 그래프가 $K$분 그래프이면 Yes를, 아니면 No를 출력한다.

닫힌 보행은 시작점과 끝점이 같은 보행을 말하며, 같은 정점과 간선을 여러 번 방문할 수 있다.