给定一个包含 N 个顶点和 M 条边的有向图（不一定是简单图），顶点编号为 1, 2, \dots, N。

第 i 条边 (1 \le i \le M) 从顶点 U_i 指向顶点 V_i，其花费（权值）为 C_i。

此外，图中每个顶点的出度最多为 4。

请找出所有满足以下条件的顶点 v (1 \le v \le N)：

从顶点 1 到顶点 v 存在一条路径，同时满足以下两个条件：

1. 该路径恰好经过 L 条边。（如果同一条边被经过多次，则每次经过都要计算在内。）
2. 路径上经过的边的花费之和至少为 S 且至多为 T。（如果同一条边被经过多次，其花费每次都要累加。）

---

什么是出度？

顶点 u 的出度是指从顶点 u 出发的边的数量。即使有多条边指向同一个顶点，它们也是分别计算的。

---

约束条件

• 1 \le N \le 2 \times 10^5
  
• 1 \le M \le 2 \times 10^5
  
• 1 \le L \le 10
  
• 1 \le S \le T \le 10^9
  
• 1 \le U_i, V_i \le N
  
• 1 \le C_i \le 10^8
  
• 每个顶点的出度最多为 4。
  
• 所有输入数值均为整数。
  

---

输入

输入由标准输入给出，格式如下：

N \ M \ L \ S \ T

U_1 \ V_1 \ C_1

U_2 \ V_2 \ C_2

\vdots

U_M \ V_M \ C_M

---

输出

按升序打印所有满足条件的顶点编号，中间用空格分隔。

如果没有顶点满足条件，请打印一个空行。

---

样例 1 解释

给定的图如左下角所示。每条边的花费标注在该边的起点附近。

在此例中，情况如下：

• 关于顶点 1： 考虑路径 1 \to 2 \to 5 \to 1。这条路径恰好经过 3 条边，总花费为 20+10+70=100，在 [80, 100] 范围内，因此满足条件。
  
• 关于顶点 2： 从顶点 1 到顶点 2 不存在满足条件的路径。例如路径 1 \to 2 \to 1 \to 2 虽然经过 3 条边，但花费为 20+30+20=70，小于 80，不满足条件。
  
• 关于顶点 3： 路径 1 \to 2 \to 1 \to 3 经过 3 条边，但花费为 20+30+70=120，大于 100，不满足条件。
  
• 关于顶点 5： 考虑路径 1 \to 3 \to 2 \to 5。这条路径恰好经过 3 条边，总花费为 70+10+10=90，在 [80, 100] 范围内，满足条件。
  

因此，按升序输出 1 5。

样例 3 提示

图可能包含自环（从自己指向自己的边）和重边（多条边连接相同的两个点）。

在这个测试用例中，顶点 1 的出度为 4，顶点 2 的出度为 1。

思路

由于路径小于10，且每个点的出度为4，所以至多4^{10} = (2^2)^{10} = 2^{20} \approx 1,000,000因此直接DFS，方案可行就标记，从1出发，长度超过或者深度超过返回，长度等于就看看符合不符合，长度小于就标记，最后统一输出

代码

// Sunshine sunshine ladybugs awake,

// Clap your hooves and do a little shake.

#ifdef _GLIBCXX_DEBUG

#undef _GLIBCXX_DEBUG

#endif

#ifdef _GLIBCXX_DEBUG_PEDANTIC

#undef _GLIBCXX_DEBUG_PEDANTIC

#endif

#include <bits/stdc++.h>

#define int long long

using namespace std;

  

const int MAXN=2000010;

struct Node{

    int to,cost;

};

vector<Node> adj[MAXN];

int vis[MAXN];

int n,m,l,s,t;

  

void DFS(int u,int d,int len){

    if(d>l||len>t)return ;

    if(d==l&&len>=s&&len<=t){

        vis[u]=true;

        return ;

    }

    for(auto [to,cost]:adj[u]){

        DFS(to,d+1,len+cost);

    }

}

  
  

void solve() {

    cin>>n>>m>>l>>s>>t;

    for(int i=0;i<m;i++){

        int u,v,c;

        cin>>u>>v>>c;

        adj[u].push_back({v,c});

    }

    DFS(1,0,0);

    for(int i=1;i<=n;i++){

        if(vis[i])cout<<i<<" ";

    }

    cout<<endl;

}

  

signed main() {

    ios_base::sync_with_stdio(false);

    cin.tie(nullptr);

    // freopen("input.txt", "r", stdin);

    // freopen("output.txt", "w", stdout);

    //int t; cin >> t; while (t--) solve();

    solve();

    return 0;

}