問題概要 駅$ 1 $から駅$ N $までの$ N $個の駅に対し，$ M $個の路線が存在する． $ i $番目の路線は駅$ p_i $と駅$ q_i $を相互に結び，会社$ c_i $によって運営されている． 駅$ 1 $を出発地，駅$ N $を目的地とするとき，異なる会社の路線への最小の乗り…