第一届CCF真题+部分答案10版

输出格式

输出m行，分别代表每一条旅行方案的最小花费。 样例输入 6 4

1 7 3 2 5 6 1 2 4 1 3 5 2 4 1 3 5 2 3 6 1 2 5 4 6 6 4 5 6

样例输出 35 16 26 13

样例说明

对于第一条路线，小R会经过2->1->3->5。其中在城市2处以7的价格购买4单位粮食，到城市1时全部吃完，并用1的价格购买7单位粮食，然后到达终点。 评测用例规模与约定

前10%的评测用例满足：n, m ≤ 20, wi ≤ 20； 前30%的评测用例满足：n, m ≤ 200；

另有40%的评测用例满足：一个城市至多与其它两个城市相连。

所有评测用例都满足：1 ≤ n, m ≤ 105，1 ≤ wi ≤ 106，1 ≤ e ≤ 10000。