Shortest Path with Limited Direction Changes

You are given a weighted undirected graph with n nodes and m edges. In addition to finding the standard shortest path between a start node s and an end node e, you are also given an integer k which represents the maximum allowed number of direction changes along the path.

A direction change is counted every time you continue from one edge to the next if the next edge does not directly backtrack to the previous node. More formally, if you arrive to a node from a previous node p and then travel to a neighbor that is not p, it is considered a direction change (except for the very first move from the start). Your task is to compute the minimum cost path from s to e while not exceeding k direction changes. If no valid path exists under these conditions, output -1.

Note: The input is provided via standard input (stdin) and output should go to standard output (stdout).

inputFormat

The input is given in the following format via standard input:

n m s e k
u1 v1 w1
u2 v2 w2
... (m lines in total)

Here,

• n: Number of nodes (nodes are numbered from 1 to n).
• m: Number of edges.
• s: Start node.
• e: End node.
• k: Maximum allowed direction changes.
• Each of the next m lines contains three integers u v w representing an undirected edge between nodes u and v with weight w.

outputFormat

Output a single integer which is the length of the shortest path from s to e that does not exceed k direction changes. If there is no valid path, output -1.

5 7 1 5 2
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
4 5 3
2 5 7

10