In the language of graph theory, we are given a graph with ~N~ nodes and ~M~ edges. Each edge has an integer label, which we will refer to as its weight.

For ease of discussion, we will use the graph given in the sample input, shown below, as an example throughout.

Subtask 1

Here, we are given a connected graph on ~N~ nodes and ~N-1~ edges. Thus the given graph is a tree, so there is only one path from node 1 to node ~N~ that doesn't reuse any edges. We should never double back on our path, only changing our chilling level when necessary. Thus we can simply compute the cost incurred by traversing the simple path from node 1 to node ~N~.

Subtask 2

Notice that our state in the dungeon is entirely determined by the pair ~(u,L)~ where ~u~ is the node we are at and ~L~ is our boots' chilling level.

Since all edge weights are between 1 and 10 inclusive, we should never adjust our chilling level above 10, as we would have to adjust it back down before we traverse the next edge. Similarly, we should never the level to be below 0. Thus there are only 11 chilling levels ~L~ that we need to consider. This means there are only ~11N~ possible states we can be in.

We can carefully construct an undirected graph that represents the costs to transition between these states ~(u,L)~. To construct this graph, it helps to think of all of the actions we can take at a state ~(u,L)~. We can:

• traverse an edge that has an endpoint at ~u~ and weight ~L~ at a cost of zero, or
• change the chilling level of our boots by ~+1~ or ~-1~ for a cost of 1.

Notice that we don't need to consider changing the chilling level by more than 1 at a time: we can think of the operation "pay ~d~ coins to change the chilling level of your boots by ~d~" as "pay 1 coin to change the chilling level of your boots by 1, as many times as we want".

Counting carefully, the undirected graph we construct has ~11N~ nodes and ~10N+M~ edges, and all weights are non-negative. We can use Dijkstra's algorithm to find the shortest path from the state ~(1,0)~ to all other states, and return the cheapest way to get to one of the states ~(N,x)~ for some ~x~ between 0 and 10.

Subtask 3

Before traversing an edge, we must adjust our chilling level to match the weight of the edge. Thus, for every two adjacent edges we traverse with weights ~x~ and ~y~, we must pay the cost ~|x-y|~.

Also, notice that once we have the right chilling level to traverse an edge, we essentially have access to both endpoints at the same time.

Combining these two observations, we notice that our state in the dungeon is determined by which edge ~e~ we last traversed. It doesn't matter in which direction we traversed it: conceptually, we can think of traversing ~e~ in one direction, and immediately traversing back if we so desire.

Thus we can again construct an undirected graph ~H~ that represents the costs to transition between the states ~e~. For every two edges ~e~ and ~f~ that share an endpoint, we can transition between them at a cost of ~|w(e)-w(f)|~, where ~w(e)~ and ~w(f)~ denote the weights of edges ~e~ and ~f~, respectively.

Each state ~e~ is connected to at most eight other states, because the two endpoints can each have four other edges adjacent to them. The number of edges in ~H~ is then at most ~8M~.

To account for the cost of the first edge, we should imagine that we traversed a weight-zero edge before we started our path. We can think of adding an edge ~e_0~ from node 1 to itself with weight 0 in the original graph. We then return the minimum cost to get from state ~e_0~ to any state ~e~ where ~e~ is incident to node ~N~.

Subtask 4

We try a similar thing to subtask 3, but now since the degree of a node can be much higher than 5, the ~H~ we would construct may have too many edges.

The main idea is to reduce the number of edges in the graph we construct. Consider node 3 in the sample graph. The state transitions constructed from the edges incident to node 3 are:

• the transition between edge ~(3,2)~ and ~(3,4)~ with cost ~|2-3|=1~,
• the transition between edge ~(3,2)~ and ~(3,1)~ with cost ~|2-6|=4~, and
• the transition between edge ~(3,4)~ and ~(3,1)~ with cost ~|3-6|=3~.

Notice that the second transition is already "covered" by the other two. If our chilling level is at 2 and we want to move from ~(3,2)~ to ~(3,1)~, it does not cost us anything to make a "pit stop" at ~(3,4)~ with weight 3, because we will be increasing our chilling level beyond 3 anyway. This reasoning is similar to why we only have to consider ~d=1~ in the discussion of subtask 2.

Thus way, a node with degree ~t~ only adds ~t-1~ transitions to our graph. The number of nodes and edges are both ~O(M)~ in this case.