Bessie和她的妹妹Elsie想要从谷仓旅行到他们最喜欢的地区去。她们会在同一时间离开谷仓，也希望要在同一时

间到达她们的目的地地区。农场由N个地区组成，分别编号为1..N (1 <= N <= 100)，谷仓位于1号区域，而她们的

目的地是N号区域。由于农场是依山而建的，两个区域之间会有高度差，编号小的地区海拔高于编号大的地区的海

拔，即1号地区海拔最高，N号地区海拔最低。会有M条小路两两连接不同地区。因为山路过于陡峭，路只允许以下

坡的方式行走。比如就一条路连接了5号区域和8号区域，那么只允许从5号区域前往8号区域而不允许反向行走。每

两个地区之间至多只有一条路，所以M <= N(N-1)/2。Bessie和Elsie走路所花费的时间是不一样的。比如，走同一

条路，Bessie会需要10个单位时间，而Elsie会要20个。请注意，因为她们在赶时间，所以只会在路上花费时间，

进入或者离开一个区域不需要花费时间，而且她们也不会停下来等对方。请帮忙计算出Bessie和Elsie最短需要多

少时间才能同时出发且同时到达她们的目的地。