트리

사샤는 얼마 전 정보 수업에서 이진 탐색 트리를 배웠다. 이진 탐색 트리는 각 정점에 키라고 부르는 수가 적힌 이진 트리다. 정점의 키는 왼쪽 부분 트리의 모든 키보다 크고, 오른쪽 부분 트리의 모든 키보다 작다.

이런 트리를 쓰면 수들의 집합을 저장하고, 특정 수가 집합에 속하는지 효율적으로 확인할 수 있다. 사샤는 이미 이진 탐색 트리를 구현했다. 하지만 집합을 저장하는 것은 그리 흥미롭지 않았다. 그녀가 원한 것은 연관 배열이다. 연관 배열에서는 각 키마다 값이라는 다른 수가 함께 저장된다. 이 경우 각 정점에는 키와 값, 두 수가 들어가고, 트리는 정점의 키를 기준으로 이진 탐색 트리가 된다.

사샤는 각 정점에 수를 하나만 저장하는 연관 배열 구조를 원한다. 그래서 키와 값의 쌍을 저장하는 이진 탐색 트리에 다음 연산을 정의했다. 정점의 왼쪽 자식의 새 키는 그 정점의 키가 된다. 오른쪽 자식의 새 키는 그 정점의 값이 된다. 연산 전에 정점에 왼쪽 또는 오른쪽 자식이 없었다면, 그 자식이 새로 생겨서 해당하는 키를 받는다. 루트의 새 키는 어떤 수 $T$가 된다.

주어진 이진 탐색 트리의 정점 값은 알려주지 않는다. 위 연산을 적용한 뒤의 트리가 이진 탐색 트리가 되도록 하는 값의 조합을 하나 출력하라. 각 값은 $1$ 이상 $10^9$ 이하의 정수다. 그런 값이 존재하지 않으면 불가능하다고 판단하라.

첫 줄에 공백으로 구분된 두 정수 $n$과 $T$가 주어진다($1 \le n \le 10^5$, $1 \le T \le 10^9$). $n$은 원래 트리의 정점 수이고, $T$는 새 트리에서 루트의 키다.

다음 $n$개 줄에는 정점 정보가 주어진다. $i$번째 줄에는 세 정수 $l_i$, $r_i$, $a_i$가 주어진다($1 \le l_i \le n$, $0 \le r_i \le n$, $0 \le a_i \le 10^9$). 각각 정점 $i$의 왼쪽 자식 번호, 오른쪽 자식 번호, 정점 $i$의 키다. 자식이 없으면 해당 값은 0이다. 첫 번째 정점이 트리의 루트다.

그런 값이 존재하지 않으면 첫 줄에 $-1$을 출력한다. 존재하면 각 정점의 값을 정점 순서대로 $n$개 출력한다. 각 값은 $1$ 이상 $10^9$ 이하의 정수여야 한다.