魔法师小蓝为了营救自己的朋友小 Q，来到了敌人布置的魔法阵，魔法阵可以看作是一幅具有 N 个结点 M 条边的无向图，结点编号为 0, 1, 2, . . . , N1，图中没有重边和自环，敌人在每条边上都布置了陷阱，每条边都有一个伤害属性 w，每当小蓝经过一条边时就会受到这条边对应的 w 的伤害，小蓝从结点 0出发，沿着边行走，想要到达结点 N1 营救小 Q，小蓝最多只可以使用一次上述的魔法，请问从结点 0 出发到结点 N 1 受到的最小伤害是多少？
魔法师小蓝为了营救自己的朋友小 Q，来到了敌人布置的魔法阵。魔法阵可以看作是一幅具有 N 个结点 M 条边的无向图，结点编号为 0, 1, 2, . . . , N−1，图中没有重边和自环。敌人在每条边上都布置了陷阱，每条边都有一个伤害属性 w，每当小蓝经过一条边时就会受到这条边对应的 w 的伤害。小蓝从结点 0出发，沿着边行走，想要到达结点 N−1 营救小 Q。 小蓝有一种特殊的魔法可以使用，假设一条路径按照顺序依次经过了以下L 条边：e1, e2, . . . , eL（可以出现重复的边），那么期间小蓝受到的总伤害就是P = ∑Li=1 w(ei)，w(ei) 表示边 ei 的伤害属性。如果L≥K，那么小蓝就可以从这 L条边当中选出连续出现的K条边 ec , ec+1, . . . , ec+K−1并免去在这K 条边行走期间所受到的伤害，即使用魔法之后路径总伤害变为 P ′ = P −∑c+K−1i=cw(ei)。 注意必须恰好选出连续出现的 K 条边，所以当 L < K 时无法使用魔法。 小蓝最多只可以使用一次上述的魔法，请问从结点 0 出发到结点 N − 1 受到的最小伤害是多少？题目保证至少存在一条从结点 0 到 N − 1 的路径。
（图片来源网络，侵删）
