Mimori知道了，只有毁灭掉神树，才能保护Yuuna和大家。但是，想要到神树那里需要穿越树海，树海非常危险，需要携带一定量的精灵才能通过。
她把树海抽象为一张有n个点和m条边的无向连通图，无重边和自环，结点编号为1~n，结点之间有双向道路连接。
每个结点有一个精灵需求数，u结点的精灵需求数记作w[u]。
通过这些边要支付一定数量的精灵！费用规定如下：
①若是普通道路(记作类别0)，她需要支付1只精灵。
②若是特殊道路(记作类别1)，她需要支付自己当前携带的精灵数的1/20，若不满20只则按20只计算。(例如、若她身上此时有10只精灵，则需要支付1只；若有69只精灵，则需要支付4只。)
她定义了一个整数S，令S等于每对结点之间的最优路径长度之和。我们用d(u,v)表示u,v之间的最优路径长度，d(u,v)被定义为从u沿路径到达v，且身上至少还有w[v]只精灵的前提下，初始携带的的最少精灵数(注意!仅仅在边上要支付精灵,在结点处不支付,但是你需要满足终点的精灵需求数)。(例如、结点数等于3时，S=d(1,1)+d(1,2)+d(1,3)+d(2,1)+d(2,2)+d(2,3)+d(3,1)+d(3,2)+d(3,3))
那么问题来了，她想删除一条边后使得新的S值S’最大。当然，你必须保证删除后图仍然连通才行。
BZPRO