Given a graph $ G(V,E)$ with $ n$ vertices labeled $ 1,2,…n$ and $ m$ positively weighted edges $ (u,v,w)$ with the condition that $ u<v,$ $ \forall u,v \in G$ , so the graph we are considering is actually a DAG. We need to find an odd path from $ 1$ to $ n$ that have the smallest weight median. i.e when the weights on the path are listed and sorted, the median of that list should be minimal.

Is it possible to solve this problem without enumerating all possible odd paths while maintaining a running median?

I have been trying to solve this problem for a couple of days and got stuck and solutions are not posted on the website.

Problem source: Problem G