Choosing a Room

Hyeonseo, a freshman, has a lot on their mind again this semester. The biggest worry is that many morning classes make it hard to reach the lecture hall on time. After some thought, Hyeonseo decided to rent a room near school.

The area around the school is a graph with $N$ vertices and $M$ edges. The school is at vertex 1, and every other vertex has one room that Hyeonseo could rent. An edge is a road between the school and a room, or between two rooms. Roads can be used in both directions.

Each road has a traffic value. Crossing a road with traffic $x$ takes $x$ minutes in either direction. Traffic is not fixed because of various events. Specifically, the traffic on road $i$ is $a_i$ with probability 1/2 and $b_i$ with probability 1/2. Each road's traffic is chosen independently, and it can change every time Hyeonseo walks along the road. $a_i$ or $b_i$ may be negative, in which case time runs backward when crossing that road.

For every vertex $i$ other than vertex 1, let $W_i$ be the set of all possible walks from vertex $i$ to vertex 1.

• A walk from $s$ to $e$ starts at $s$, follows connected roads only, and ends at $e$.
• A walk may reuse the same road any number of times. Reaching vertex 1 does not require stopping there.

For each $2 \le i \le N$, define $f_i : W_i \to \mathbb{R}$ by

$f_i(w)$ = (the expected time in minutes to reach vertex 1 from vertex $i$ by following walk $w$)

Here $\mathbb{R}$ is the set of all real numbers.

Hyeonseo only considers vertices $i$ for which some $w \in W_i$ satisfies $f_i(w) \le T$. Find all rooms that satisfy this condition.

The first line contains the number of vertices $N$ and the number of edges $M$ ($1 \le N, M \le 200000$).

Each of the next $M$ lines contains two vertices $u_i$ and $v_i$ joined by edge $i$, followed by integers $a_i$ and $b_i$, separated by spaces. ($1 \le u_i, v_i \le N$; $u_i \ne v_i$; $-10^9 \le a_i, b_i \le 10^9$) No pair of vertices is joined twice. That is, for all $1 \le i, j \le M$, if $\{u_i, v_i\} = \{u_j, v_j\}$ then $i = j$.

Line $M+2$ contains the integer $T$ ($-2 \times 10^{15} \le T \le 2 \times 10^{15}$).

The first line contains the number $K$ of rooms that satisfy the condition. If no room satisfies it, print 0.

If the first line is not 0, the second line lists the vertex numbers of the rooms that satisfy the condition in ascending order, separated by spaces.

In the first example, for vertex 2, the walk 2 → 3 → 1 gives an expected time of 4 minutes. For vertex 3, the walk 3 → 1 gives an expected time of 2.5 minutes. As the third example shows, some rooms may be unreachable from the school.