자취방 정하기

새내기 현서는 이번 학기에도 고민이 많다. 가장 큰 고민은 아침 수업이 많아서 수업 시간에 맞춰 강의실에 도착하지 못할 것 같다는 점이다. 고민 끝에 현서는 학교 주변에 자취방을 하나 구하기로 했다.

학교 주변은 정점이 $N$개, 간선이 $M$개인 그래프로 표현된다. 학교는 1번 정점에 있고, 나머지 정점에는 현서가 계약할 수 있는 자취방이 하나씩 있다. 간선은 학교와 자취방, 또는 자취방과 자취방 사이의 도로를 나타낸다. 도로는 양방향으로 모두 사용할 수 있다.

각 도로는 교통량이라는 값을 가진다. 교통량이 $x$인 도로를 통과하는 데에는 양방향 모두 $x$분이 걸린다. 여러 사건 때문에 각 도로의 교통량은 매번 일정하지 않다. 구체적으로 $i$번 도로의 교통량은 절반의 확률로 $a_i$, 나머지 절반의 확률로 $b_i$가 된다. 교통량은 각 도로마다 독립적으로 정해지며, 현서가 길을 지날 때마다 바뀔 수 있다. $a_i$ 또는 $b_i$는 음수일 수도 있다. 이 경우에는 도로를 통과할 때 시간이 거꾸로 흐른다고 생각하면 된다.

1번 정점을 제외한 모든 정점 $i$에 대해, $W_i$를 $i$번 정점에서 1번 정점으로 가는 모든 가능한 이동의 집합이라고 하자.

• $s$에서 $e$로의 이동은 $s$에서 출발하여 연결된 간선만을 따라 움직여 $e$에 도착하는 것이다.
• 이동에서는 같은 간선을 여러 번 사용하는 것도 허용된다. 도착 정점인 1번 정점에 도달했다고 해서 반드시 멈출 필요는 없다.

모든 $2 \le i \le N$에 대해 함수 $f_i : W_i \to \mathbb{R}$을

$f_i(w)$ = ($i$번 정점에서 이동 $w$를 이용하여 1번 정점으로 갈 때 걸리는 분 단위 시간의 기댓값)

으로 정의하자. 이때 $\mathbb{R}$은 실수 전체의 집합이다.

현서는 $f_i(w) \le T$인 $w \in W_i$가 존재하는 정점만을 고려하려고 한다. 현서를 위해 위 조건을 만족하는 자취방을 모두 구해주자.

첫째 줄에 정점의 개수 $N$과 간선의 개수 $M$이 주어진다. ($1 \le N, M \le 200000$)

둘째 줄부터 $M$개의 줄에 걸쳐 각 간선이 잇는 두 정점의 번호 $u_i$, $v_i$와 정수 $a_i$, $b_i$가 공백으로 구분되어 주어진다. ($1 \le u_i, v_i \le N$; $u_i \ne v_i$; $-10^9 \le a_i, b_i \le 10^9$) 같은 정점 쌍을 두 번 잇는 입력은 주어지지 않는다. 즉, 모든 $1 \le i, j \le M$에 대해 $\{u_i, v_i\} = \{u_j, v_j\}$이면 $i = j$이다.

($M+2$)째 줄에 정수 $T$가 주어진다. ($-2 \times 10^{15} \le T \le 2 \times 10^{15}$)

첫째 줄에 조건을 만족하는 자취방의 개수 $K$를 출력한다. 조건을 만족하는 자취방이 없으면 0을 출력한다.

첫째 줄에 0이 아닌 값을 출력했다면, 둘째 줄에 조건을 만족하는 자취방이 위치한 정점의 번호를 공백으로 구분하여 오름차순으로 출력한다.

첫 번째 예제에서, 2번 정점의 경우 2 → 3 → 1 순으로 이동하면 기댓값이 4분이 된다. 3번 정점의 경우 3 → 1 순으로 이동하면 기댓값이 2.5분이 된다. 세 번째 예제에서 주어지듯이, 학교에서 도달할 수 없는 자취방이 함께 주어지는 것도 가능하다.