料金所を点、道路を辺に見立てた無向グラフを考えます。この問題において、「鋭角になるような乗り換えはできない」という条件がなければ通常の単一始点最短経路問題となるので、ダイクストラ法などで解くことができます。
しかし、本問題ではこの条件を考慮する必要があるのでただダイクストラ法をするだけでは解くことができません。

ある経路において鋭角が発生する場合、鋭角を作る $3$ 点のみが重要であって、他の経路上の点は重要ではありません。言い換えると、今いる点と $1$ つ前にいる点がわかれば、次に行くことが可能な点とそうでない点がわかるということです。
そこで、拡張ダイクストラという概念を用います。これは、グラフに複数の情報を持たせたグラフ $G'$ を元のグラフ $G$ から作り、 $G'$ において最短経路問題をダイクストラ法の要領で解くというものです。もしくは通常のダイクストラ法では C++ ならば priority_queue などに距離と今いる頂点の情報を保存しますが、この情報の種類を増やすともいうことができます。

さて、本問題では距離と $1$ つ前にいた頂点、今いる頂点の $3$ つの情報のみが重要なので、これらを priority_queue に保存するような拡張ダイクストラ法で解くことができます。最後に、鋭角となるかの判定を考えます。

$3$ 点 $P,Q,R$ について $p=QR,q=RP,r=PQ$ とした場合、余弦定理より $q^2=p^2+r^2-2pr \cos \angle PQR$ が成立します。 $0^{\circ} < \angle PQR < 90^{\circ}$ において $ \cos \angle PQR > 0$ より、 $q^2 < p^2+r^2$ となります。 $P,Q,R$ が入力に即した点の場合、 $p^2,q^2,r^2$ は整数となるため誤差を気にすることなく判定が $O(1)$ で行えます。

以上より、この問題は \(O(n(n+m))\) で解くことができました。