Description

The road safety department is planning to deploy a road monitoring system from City A to City B to improve its ability to respond to emergencies. The road network from City A to City B can be described as an undirected graph $G=(V, E)$, where $V$ is the set of nodes in the road network, and $E$ is the set of bidirectional roads connecting the nodes. All nodes are numbered from $1$ to $n$, where $n$ is the number of nodes. City A is located at node $s$, and City B is located at node $t$.

The department plans to install monitoring equipment on some roads to reduce the response difficulty of the entire road network. When an emergency occurs, the department needs to dispatch personnel to some roads for duty, such that any path from node $s$ to node $t$ passes through at least one monitored road (a road with monitoring equipment installed or a road with personnel on duty). Therefore, the response difficulty is defined as the minimum number of roads that need to be assigned personnel so that any path from $s$ to $t$ passes through at least one monitored road.

Due to different natural environments, the cost of installing monitoring equipment on different roads may vary. Specifically, for an edge $e$, the cost of installing equipment is $W(e)$. Due to limited funding, they hope to find a plan such that the response difficulty of the road network does not exceed $k$. Please help them find the most economical deployment plan possible.

Input

This is an "answer submission" problem. There are 10 input files named road*.in in your directory.

The first line of the input file contains three integers $n$, $m$, and $k$, representing the number of nodes, the number of roads, and the upper limit of the response difficulty, respectively.

The second line of the input file contains two integers $s$ and $t$, representing the node numbers of City A and City B.

The next $m$ lines each contain three positive integers $a_i$, $b_i$, and $w_i$, representing a road connecting node $a_i$ and node $b_i$, with an installation cost of $w_i$.

Output

For each input file, provide the corresponding output file road*.out in the directory.

The first line of the output file contains a value $s$, representing the number of roads on which monitoring equipment will be installed in your plan. The next $s$ lines each contain an integer $p_i$, representing that monitoring equipment is installed on the $p_i$-th road in the input file (edges are numbered starting from 1).

Examples

Input 1

3 3 1
1 3
1 2 1
2 3 10
1 3 5

Output 1

1
1

Subtasks

For each test case, if you do not provide an output or the output is invalid, you will receive 0 points.

For each test case, we have five scoring parameters $m_1, m_2, m_3, m_4$, and $m_5$. Assuming the cost of the participant's plan is $c$:

• If $c < m_1$, you get 12 points;
• If $c = m_1$, you get 10 points;
• If $m_1 < c \le m_2$, you get 8 points;
• If $m_2 < c \le m_3$, you get 5 points;
• If $m_3 < c \le m_4$, you get 3 points;
• If $c < m_5$, you get 1 point;
• Otherwise, you get 0 points.

Implementation Details

There is a program named checker in your directory that can be used to check your output. You can use the following command in the terminal to check your output:

./checker N

Where $N$ is the test case number. For example, to test the 3rd test case, you can use:

./checker 3

This program will check whether your output is valid. If the plan is valid, the program will also provide the total deployment cost of the plan.