每年春季，在某岛屿上都会举行游行活动。
在这个岛屿上有 个城市， 条连接着城市的有向道路。
你要安排英雄们的巡游。英雄从城市 出发，经过若干个城市，到城市 结束，需要特别注意的是，每个英雄的巡游的 可以和 相同，但是必须至少途径 个城市。
每次游行你的花费将由 部分构成：
- 每个英雄游行经过的距离之和，需要特别注意的是，假如一条边被途径了 次，那么它对答案的贡献是 ，表示这条边的边权。
- 如果一个英雄的巡游的 不等于 ，那么会额外增加 的费用。因为英雄要打的回到起点。
- 如果一个城市没有任何一个英雄途经，那么这个城市会很不高兴，需要 费用的补偿。
你有无数个的英雄。你要合理安排游行方案，使得费用最小。
由于每年， 值都是不一样的。所以你要回答 个询问，每个询问都是，当 为当前输入数值的时候的答案。
