Consider the following Dynamic Programming (DP).

The minimum sum of lengths of roads on the path from town \(1\) to \(u\) such that the indices of the used roads is a subsequence of \((E_1, \dots, E_i)\).

As \(i\) increases, we have more paths in which the sequence of indices of used roads is a subsequence of \((E_1, \dots, E_i)\). Considering \(i = k\) and \(i = k+1\), the new path is described by:

A path with \(i=k\) that ends at vertex \(A_{E_{k + 1}}\), succeeded by edge \(E_{k+1}\).

Therefore, the transition of DP is as follows:

First, initialize with \(\text{dp}[i + 1][u] :=\text{dp}[i][u]\).

Then, replace \(\text{dp}[i + 1][B_{E_{i + 1}}]\) with \(\min(\text{dp}[i + 1][B_{E_{i + 1}}], \text{dp}[i][A_{E_{i + 1}}] + C_{E_{i + 1}})\).

Computing it does not require an array of size \(NK\); we may prepare an array of length \(N\) and reuse as we update them in-place.
The complexity is \(O(N + M + K)\).

Sample code (C++)