Description

小明镇上的游乐场是一个图的结构，有 $n$ 个点， $m$ 条边，每条边有不同的长度，然后每个点都有一个小卖部，小卖部出售汉堡或者可乐（但只会出售一种，且小明只会买一个）。

小明认为，逛游乐园不能没有吃的或者喝的，所以他每到一个位置（包括起终点），就会在这个地方的小卖部买东西吃或者喝。

但是饮食搭配是要均衡的，小明深知这一点，所以他不希望会在某个地方使得吃过的汉堡比喝过的可乐多 $>k$ 个，或者少于 $>k$ 个。

所以现在小明想知道，从起点到终点，在饮食均衡（确信）的条件下，最短需要走多长的路，无法到达输出 $-1$ 。

数据范围：

且每个样例点的大数据不超过 $2$ 个。