Problem Description

The road safety department recently plans 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 devices on some roads, in order to reduce the overall response difficulty of the road network. When an emergency happens, the department needs to assign personnel to be on duty on some roads, so that any path from node $s$ to node $t$ passes through at least one monitored road (a road with a monitoring device installed, or a road with personnel on duty). Therefore, the response difficulty is defined as the minimum number of roads that need personnel to be assigned, 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 devices on different roads may also differ. Specifically, for an edge $e$, the installation cost is $W(e)$. Since the budget is limited, they want to find a plan such that the response difficulty of the road network does not exceed $k$. Please help them find a deployment plan that is as economical as possible.

Input Format

This is an output-only problem. There are $10$ input files road*.in in your directory.

The first line of each 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.

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

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

Output Format

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$, indicating that in the contestant’s plan, monitoring devices will be installed on $s$ roads. The next $s$ lines each contain an integer $p_i$, indicating that a monitoring device is installed on the $p_i$-th road in the input file (edges are numbered starting from $1$).

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

1
1

Hint

For each test case, if you do not output anything or your output is invalid, you will get $0$ points.

For each test case, we have five scoring parameters $m_1$, $m_2$, $m_3$, $m_4$, and $m_5$. Suppose the total cost of the contestant’s plan is $c$.

• If $c<m_1$, you get $12$ points. (Note: in the actual contest, this was $10$ points.)
• If $c=m_1$, you get $10$ points.
• If $m_1<c\leq m_2$, you get $8$ points.
• If $m_2<c\leq m_3$, you get $5$ points.
• If $m_3<c\leq m_4$, you get $3$ points.
• If $c<m_5$, you get $1$ point.
• Otherwise, you get $0$ points.

Translated by ChatGPT 5