baltazar (COCI CONTEST_#3)
Time limit: 4 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: shortest path, dijkstra, graph theory

# Task Baltazar

Baltazar decided to go on a vacation. Currently, he is in Baltazargrad and wants to travel to Primošten. To get there, he has to go through many cities. There are *n* cities, and they are connected with *m* two-way roads. Baltazargrad is labeled as city no. 1, and Primošten as city no. *n*.

Baltazar isn't sure about the route from Baltazargrad to Primošten, so he will use GPS. It will lead him to his destination using the **shortest** route.

But Baltazar really likes to travel, and he can pour his magic potion on any road (even the ones he won't pass by) and increase its length by **2** kilometers. He can pour it on **only one** road.

Soon he realized that he has to check in at the hotel Zora in Primošten before noon, so he can't increase the length of the shortest route too much. Now, he wants to know how many roads can he pour his magic potion on, so that the shortest distance between Baltazargrad and Primošten increases by **exactly 1** kilometer.

Help him determine the roads he can pour his magic potion on.

## Input

Each test contains multiple test cases. The first line contains the number of test cases *t* (1 ≤ *t* ≤ 10 000). The description of the test cases follows.

The first line of each test case contains integers *n* and *m* (2 ≤ *n* ≤ 300 000, 1 ≤ *m* ≤ min(300000, n*(n-1)/2)), the number of cities, and the number of roads between cities.

The following *m* lines contain integers *a<sub>i</sub>*, *b<sub>i</sub>*, and *w<sub>i</sub>* (1 ≤ *a<sub>i</sub>*, *b<sub>i</sub>* ≤ *n*, *a<sub>i</sub>* ≠ *b<sub>i</sub>*, 1 ≤ *w<sub>i</sub>* ≤ 10<sup>9</sup>), meaning there is a road between cities *a<sub>i</sub>* and *b<sub>i</sub>*, and its length is *w<sub>i</sub>*. Between each pair of cities, there is at most one road connecting them.

All the cities are connected, i.e., for each pair of cities, there is a path from one to another, but not necessarily direct.

It is guaranteed that the sum of *n* over all test cases does not exceed 300 000, and that the sum of *m* over all test cases does not exceed 300 000.

## Output

In the first line, print the integer *c*, the number of roads on which Baltazar can pour his magic potion. In the second line, print *c* integers, the indices of the roads in **increasing** order.

## Scoring

| Subtask | Points | Constraints                                                                                                                                                           |
|---------|--------|-----------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 1       | 15     | *n*, *m* ≤ 1 000                                                                                                                                                   |
| 2       | 30     | There is a road between Baltazargrad and Primošten, and its length is 1 kilometer longer than the shortest distance between these cities. |
| 3       | 65     | No additional constraints.                                                                                                                                            |

## Examples

**Input**
```
3
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
6 6
1 2 2
1 3 2
2 4 2
3 5 2
4 5 3
5 6 2
6 7
1 2 2
1 3 2
2 4 2
3 5 2
4 5 1
5 6 2
1 6 7
```

**Output**
```
2
2 4
0
3
2 4 6
```

**Clarification of the example:**

The cities and the roads are shown in the image. If Baltazar pours his magic potion on road 2 (between cities 1 and 3), or on road 4 (between cities 3 and 5), then the shortest distance between cities 1 and *n* will increase by 1.

![](_page_1_Figure_10.jpeg)

Starter code:

Grader code:

Setup script:

Evaluation script: