P9758 [COCI 2022/2023 #3] Baltazar

Baltazar is getting ready to go on vacation. He is currently in Baltazargrad and wants to travel to Primosten. To get there, he needs to pass through many cities. There are $n$ cities connected by $m$ bidirectional roads. Baltazargrad is numbered $1$, and Primosten is numbered $n$. Baltazar is not sure which route to take from Baltazargrad to Primosten, so he will use GPS, which will guide him along the shortest route. But Baltazar really loves traveling, and he can use a magic potion on any road (even if he does not travel on it) to increase the road’s length by $2$ kilometers. However, he can only use the potion once. Soon he realizes that he must check into the Zora hotel in Primosten before noon. So he cannot increase the total length of the shortest path too much. He now wants to know how many roads he can use the potion on such that the length of the shortest path increases by exactly $1$ kilometer.

Multiple test cases. The first line contains an integer $t$, the number of test cases. Then for each test case, the first line contains two integers $n,m$, representing the number of cities and the number of roads between the cities. The next $m$ lines each contain three integers $a_i,b_i,w_i$, representing a road connecting cities $a_i,b_i$ with length $w_i$. There is at most one road between any pair of cities. It is guaranteed that all cities are connected. That is, for any pair of cities, there exists a path between them, but it may not be directly connected. It is guaranteed that the sums of $n$ and $m$ over all test cases are each at most $300000$.

The first line outputs an integer $c$, the number of roads on which Baltazar can use the magic potion. The next line outputs $c$ integers, in increasing order of road index, listing all roads that satisfy the condition.

**Sample Explanation** The cities and roads are shown in the figure. If Baltazar uses his magic potion on the second road (connecting cities $3$ and $5$), then the shortest distance between city $1$ and city $n$ will increase by $1$.  **Constraints** | Subtask | Points | Special Property | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n,m \leq 1000$ | | $2$ | $30$ | There is a road between the start and the end, and its length is exactly $1$ kilometer longer than the shortest route between the two cities. | | $3$ | $65$ | No special property. | For $100\%$ of the testdata, $1\le t \le 10000,2\leq n \leq 3\times10^5,1\le m\le \min(3\times 10^5,\dfrac{n\times (n-1)}{2}), 1\le a_i,b_i\le n,a_i\neq b_i,1\le w_i\le 10^9$. This problem has a full score of $110$ points. Translated by ChatGPT 5