When the given cities and canals are regarded as an undirected graph, the edges of the graph can be split into a single cycle and a forest.

Consider a cargo that should be delivered from vertex \(x\) to vertex \(y\).
Let \(x'\) be the nearest vertex in the cycle from \(x\). We define \(y'\) in the same way.

The edges in the forest

One can determine if each edge in the forest should be used or not instantly in the following way.

• If \(x' = y'\): It is optimal to deliver it on the shortest path in the connected component of the forest that both vertex \(x\) and vertex \(y\) belongs.
• If \(x' \neq y'\):
  There are two options for the cycle part, but for the edges in the forest, only those between \(x - x'\) and \(y-y'\) are used.

When actually checking if each edge will be used, one can adopt the algorithm of finding the least common ancestor (LCA) of a tree and the cumulative sum trick on a tree (where cumulative sums is calculated at last from the leaves to the root, so that the addition for a vertex is transformed into an addition to all the edges on the path to the root) in a total of \(O(N \log(N))\) time.

The edges in the cycle

In the cycle, every cargo is delivered from \(x'\) to \(y'\), but there are two choices on which side to use for each cargo.
Here, let us fix an edge \(s\) on the cycle to avoid. Then, each cargo should be delivered from \(x'\) to \(y'\) without passing \(e\), so the path is uniquely determined.
Shift the edge \(s\) one by one until it makes a round of the cycle, while calculating the sum of weights of edges to be used for each \(s\), the one can find the optimal solution.
In the course of making a circuit, the path of each cargo changes only twice (when \(s\) passes by \(x'\) and by \(y'\)).
Therefore, it is sufficient to process the following query \(O(N+M)\) times. (We regard that numbers are written on the edges on the cycle)

• Add \(1\) to some specific consecutive edges on the cycle
• Subtract \(1\) from some specific consecutive edges on the cycle
• Find the sum of weights of each edges with a non-zero number written on it

One can cut the cycle at an arbitrary position to boil it down to a problem on a one-dimensional sequence (The queries over the cut position can be split into two):

• Given are two sequences, \(a\) (initialized with \(0\)) and \(b\) (weights)
• We are to add or subtract \(1\) to a range of \(a\) for \(O(M)\) times
• We are to find the sum of \(b_i\) for such \(i\) that \(a_i \neq 0\) for \(O(N)\) times

This can be solved with a segment tree.
For example, if we store for each node the minimum value \(\min\) of its subtree and the sum of \(b_i\) for such \(i\) that \(a_i = \min\), and hold a lazy segment tree that is capable of segment addition, one can calculate the sum of \(b_i\) for such \(i\) that \(a_i = 0\), which is sufficient (note that it is always \(a_i \ge 0\))

Also, it can be processed with an even simpler segment tree.
Due to the nature of original queries, for every subtract-by-one query for a segment, there exists an corresponding add-by-one query for exactly the same segment in the past, so one can simply add to the nodes of the segment tree corresponding to the specified segment without lazy propagation without making the value on each node negative.
Therefore, if we hold the value \(\mathrm{res}_{\mathrm{node}}\): The sum of all values under the node if a non-zero value is stored in \(\mathrm{node}\), or \(\mathrm{res}_{c_1} + \mathrm{res}_{c_2}\) if zero is stored, where \(c_1\) and \(c_2\) denote its children nodes
for each \(\mathrm{node}\), then the value of \(\mathrm{res}\) for the root corresponds to “the sum of \(b_i\) for \(i\) such that \(a_i = 0\).”

The solution using hash

This solution is easier to implement compared to the solution above.
First of all, we define a random non-negative integer \(r_i\) for each cargo \(i\).
For the edge in the forest, we do the same as the solution above, but we don’t use LCA algorithm. Instead of adding \(1\), we apply \(\mathrm{xor}\) with \(r_i\) for every edge on the paths from \(x\) and \(y\) to the root. Then, for every edge above LCA, the two values cancels with each other, so only \(x - y\) path will remain.
For the cycle, we consider in the following way.

• Write \(0\) to each edge on the cycle
• For each cargo \(i\), arbitrarily determine which side to use, and apply \(\mathrm{xor}\) with \(r_i\) for every edge to use.
• Inverting the edges to use for cargo \(i\) corresponds to \(\mathrm{xor}\)-ing \(r_i\) to every edge on the cycle, so a set of edges can be excluded if and only if they has the same value written on it currently (assuming that the hashes do not collide)

If a non-empty set of cargoes which has zero xor appears on a forest, or edges with the same xor value but different sets of cargoes appear, then the answer will be wrong.
However, if we take \(r_i\) from the range like \([0, 2^{63})\), then the probability of such collision becomes small enough to ignore.
Assuming that each \(r_i\) is chosen from \([0, 2^d)\) uniformly random, the probability of the xor of a non-empty set of cargoes becoming zero or the two xor’s of two different sets of cargoes becoming zero is \(\frac{1}{2^d}\). Therefore, we can evaluate the probability of collision as

• For edges in the forest: the probability of at least one xor value of a set of at most \(N\) cargoes is at most \(N \frac{1}{2^d}\)
  
• For edges in the cycle: The probability of collision of at least one pair of xor’s of different sets of at most \(N\) cargoes is at most \(\frac{N(N - 1)}{2} \frac{1}{2^d}\).