Let $G$ be the graph with cities as vertices and two vertices connected if the corresponding cities have a road between them, and let $G'$ be the graph obtained by removing marked edges from $G$. We want to prove given 3 cities $A$, $B$, $C$, there is a path in $G'$ between $A$ and $B$, $B$ and $C$, or $C$ and $A$. Let $X$ be the set of paths between $B$ and $C$ in $G$, and define $Y$, $Z$ similarly. Let $S=X \cup Y \cup Z$ and for each path $p \in S$ define $f(p)$ as the maximum toll on edges in $p$. Let $q \in S$ be such that $f(q)$ is minimal. Such a $q$ exists as the weights are distinct. Now note that a route going through each city must contain paths from at least two of $X$, $Y$, $Z$, so the marked edge on this route cannot be on $q$ since $f(q)$ is minimal. It follows no edge from $q$ is removed in $G'$, so we are done.