For the first subtask, we can use Dijkstra to calculate the distance between cities ~1~ and ~n~, and after that for each road we can calculate the distance between cities ~1~ and ~n~ if the length of that road is increased by ~2~ km and see if that distance is higher than the initial distance by ~1~ km, for a total time complexity of ~\mathcal{O}(m^2 \log m)~.

For the second subtask, the guarantee of that subtask tells us that, no matter which road's length is increased by ~2~ km, due to the road between ~1~ and ~n~ the length of the shortest path will be increased by at most ~1~ km, so we're looking for roads whose increase of length by ~2~ km changes the length of the shortest path between ~1~ and ~n~. So, we're looking for roads which are on all shortest paths between ~1~ and ~n~. If ~d_i~ is the length of the shortest path between ~1~ and ~i~, then let's make a directed graph in which we put an edge between ~a_i~ and ~b_i~ if ~d_{a_i}+w_i = b_i~, then each path between ~1~ and ~n~ in the new graph corresponds to a shortest path between ~1~ and ~n~, so we need to find the edges that are in all paths from ~1~ to ~n~. That can be done by comparing the number of paths from ~1~ to ~n~ with the number of paths from ~1~ to ~n~ that pass through that edge. We can use dynamic programming to calculate the number of paths from ~1~ to each vertex, as well as the number of paths from each vertex to ~n~, then the number of paths between ~1~ and ~n~ that pass through an edge between ~x~ and ~y~ is equal to the product of the number of paths from ~1~ to ~x~ and the number of paths from ~y~ to ~n~. Those numbers are very large, but we can look at them modulo ~5~ randomly generated prime numbers between ~1~ and ~10^9~. Let's calculate the probability that this method says that the total number of paths and the number of paths passing through a given edge is equal, even though in reality it isn't. For that to happen, the difference between those ~2~ numbers must be divisible by all ~5~ prime numbers we chose. It can easily be seen that the number of paths between ~1~ and ~n~ is ~< 2^n~, so their difference is ~< 2^n~, so for ~n \le 3 \cdot 10^5~ it has less than ~2 \cdot 10^4~ different prime factors. There are more than ~5 \cdot 10^7~ prime numbers up to ~10^9~. So, the chance that it's divisible by all ~5~ primes is at most ~\frac{\binom{2 \cdot 10^4}{5}}{\binom{5 \cdot 10^7}{5}} \approx 10^{-17}~, and the probability that one of the ~m~ edges gives a wrong answer is that multiplied by ~m~, so about ~3 \cdot 10^{-12}~. In practice, the probability is much smaller because it's impossible to make test cases such that the difference in the number of paths are whichever numbers we want; the number of ways to choose ~m~ numbers ~\le 2^n~ is about ~(2^n)^m~, and the number of possible graphs is about ~(n^2)^m~, which is much smaller; in practice just ~1~ prime number is enough.

For the third subtask, we also need to check for each road whether it's on all paths from ~1~ to ~n~ of length ~d_n+1~. To do that, we can check if it's on all shortest paths from ~1~ to ~n~ with a length of a different parity than ~d_n~ and make sure that that shortest path has a length of ~d_n+1~. To do that, we can replace each vertex and edge with ~2~ vertices and ~2~ edges; the new vertices will be one for paths of odd length and one for paths of even length, and we can then do almost the same thing as for the second subtask. Then a road increases the length of the shortest path by ~1~ if and only if the length of the shortest path between ~1~ and ~n~ with a length of different parity than ~d_n~ is ~d_n+1~, if it's on all shortest paths between ~1~ and ~n~ and it's not on all shortest paths between ~1~ and ~n~ with a length different parity than ~d_n~.