P省有N个城市，编号分别为1..N,烦烦家住 1号城市，N号城市是省会，P省的交通非常发达，有M条有向的高速公路连接这N个城市，第i条高速公路(1<=i<=M)从城市ui连向城市vi。
这天，烦烦想自己开车从家前往省会城市游玩.烦烦是个做事很细致的人，为了有备无患，她决定同时开着heroMap和amap这两个不同的导航软件来帮助白已完成这次旅程，这两个导航软件内部采用了不同的算法，对于第i条高速公路(1<=i<=M)，heromap 认为通过时间为Pi分钟，amap 则认为通过时间为Qi分钟。这两个导航软件会根据自己的数据来计算从当前位置到目标位置所需的短时间是多少，对于第i个城市(1<=i<=N),记heromap认为从i到N把时间为heor(i),记amap认为到i到N的最短时间为a(i)。烦烦开车途经某条高速公路(1<=i<=M)时，如果heromap认为从ui到N不应该走这条路，即hero(vi)+Pi>hero(ui),则发出一次警告，同样的，如果amap认为从ui到N不应该走这条路，即a(vi)+Qi>a(ui),也会发出一次警告。
现在烦烦希望自己选择选择一条路径，使得收到的警告总数最少，请你编程解决这一问题。