無向グラフなので，街 $N$ を始点として，動物の居る道を既に通ったかどうかを区別して，各街への最短経路長を Dijkstra 法のような動的計画法で求めればよいです． より具体的には，各街 $i$ に対して，動物の居ない道のみを通る場合の最短経路長を $\mathrm{dist}(0, i)$，動物の居る道を途中で通る場合の最短経路長を $\mathrm{dist}(1, i)$ として，これらを計算して $\mathrm{dist}(1, i)$ を出力します．

初期化は $$\mathrm{dist}(0, i) = \begin{cases} 0 & (i = N),\\ +\infty &(i \neq N), \end{cases}\quad \mathrm{dist}(1, i) = +\infty$$ として，全ペア $(x, i)$ $(x \in \{0, 1\},~1 \le i \le N)$ を未確定とします． 各反復では，$\mathrm{dist}(x, i)$ の値が最小であるような未確定ペア $(x, i)$ を $1$ つ選んで確定とし， 長さ $C$ の道で街 $i$ と結ばれた街 $j$ について，その道に動物が居なければ $$\mathrm{dist}(x, j) \leftarrow \min\{\mathrm{dist}(x, j),\, \mathrm{dist}(x, i) + C\}$$ と更新し，その道に動物が居れば $$\mathrm{dist}(1, j) \leftarrow \min\{\mathrm{dist}(1, j),\, \mathrm{dist}(x, i) + C\}$$ と更新すればよいです．

アルゴリズムの正当性は Dijkstra 法と同様に確認できます． 未確定ペアを $\mathrm{dist}(x, i)$ の値とともに管理するために優先度付きキューを用いれば，全体の計算時間は $\mathrm{O}(M \log M)$ となり，この問題が解けました．