AT_abc441_d [ABC441D] Paid Walk

$ N $ 頂点 $ M $ 辺の（単純とは限らない）有向グラフがあり、頂点は頂点 $ 1, 2, \ldots, N $ と番号付けられています。 $ i $ 番目 $ (1\leq i\leq M) $ の辺は頂点 $ U_i $ から頂点 $ V_i $ へ向かう辺で、コストは $ C_i $ です。 また、各頂点の出次数は $ 4 $ 以下です。 次の条件をみたす頂点 $ v $ $ (1\leq v\leq N) $ をすべて求めてください。 > 頂点 $ 1 $ から頂点 $ v $ への経路であって、次の条件をともにみたすものが存在する。 > > - ちょうど $ L $ 回辺を通る。このとき、同じ辺を複数回通っても良いが、通るたびに回数にカウントされる。 > - 通った辺のコストの総和が $ S $ 以上 $ T $ 以下である。（同じ辺を複数回通った場合、通るたびに総和に加算されるものとする。） 出次数 とは 頂点 $ u $ の出次数は、頂点 $ u $ から出て行く辺の数を指します。辺の向かう先が同じ頂点であるような辺であっても重ねて数えられます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ L $ $ S $ $ T $ $ U_1 $ $ V_1 $ $ C_1 $ $ U_2 $ $ V_2 $ $ C_2 $ $ \vdots $ $ U_M $ $ V_M $ $ C_M $

条件をみたす頂点を **昇順に** 空白区切りで出力せよ。 条件をみたす頂点が存在しない場合は空行を出力せよ。

### Sample Explanation 1 与えられるグラフは下図左のようになっています。各辺のコストはその辺の始点のそばに示されています。  このとき、以下のようになります。 - 頂点 $ 1 $ から頂点 $ 1 $ への経路について、頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 5 $ $ \to $ 頂点 $ 1 $ （上図中央）を考えると、これはちょうど $ 3 $ 本の辺を通り、通る辺のコストの総和は $ 20+10+70=100 $ であるため、条件をみたしています。 - 頂点 $ 1 $ から頂点 $ 2 $ への経路であって、条件をみたすような経路は存在しません。ちょうど $ 3 $ 本の辺を通るような経路としては、頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 1 $ $ \to $ 頂点 $ 2 $ が存在しますが、この経路において通る辺のコストの総和は $ 20+30+20=70 $ であり特に $ 80 $ より小さいため、条件をみたしていません。 - 頂点 $ 1 $ から頂点 $ 3 $ への経路であって、条件をみたすような経路は存在しません。ちょうど $ 3 $ 本の辺を通るような経路としては、頂点 $ 1 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 1 $ $ \to $ 頂点 $ 3 $ が存在しますが、この経路において通る辺のコストの総和は $ 20+30+70=120 $ であり特に $ 100 $ より大きいため、条件をみたしていません。 - 頂点 $ 1 $ から頂点 $ 4 $ への経路であって、条件をみたすような経路は存在しません。 - 頂点 $ 1 $ から頂点 $ 5 $ への経路について、頂点 $ 1 $ $ \to $ 頂点 $ 3 $ $ \to $ 頂点 $ 2 $ $ \to $ 頂点 $ 5 $ （上図右）を考えると、これはちょうど $ 3 $ 本の辺を通り、通る辺のコストの総和は $ 70+10+10=90 $ であるため、条件をみたしています。 よって、 $ 1 $ , $ 5 $ をこの順に出力します。条件をみたす頂点を昇順に出力する必要があることに注意してください。 ### Sample Explanation 2 条件をみたす頂点が存在しない場合は空行を出力してください。 ### Sample Explanation 3 グラフは自己ループや多重辺を含む可能性があります。 なお、このテストケースにおけるグラフの頂点 $ 1,2 $ からの出次数はそれぞれ $ 4,1 $ です。 ### Constraints - $ 1\leq N\leq 2\times 10^5 $ - $ 1\leq M\leq 2\times 10^5 $ - $ 1\leq L \leq 10 $ - $ 1\leq S\leq T \leq 10^9 $ - $ 1\leq U_i,V_i\leq N $ - $ 1\leq C_i\leq 10^8 $ - 各頂点の出次数は高々 $ 4 $ である。 - 入力はすべて整数