Online Programming Server

Problem 1107: Lucky Path

Problem ID	1107
Title	Lucky Path
pdf
Description	Alice is going to visit Bob. The city has N intersections and M bidirection roads. Alice lives in intersection 0 and Bob lives in intersection N-1. Alice thinks that the number K is a lucky number. Therefore, she wants to use exactly K edges to visit Bob. Note that she may use the same edge more than once. Help Alice to find the shortest length of the walk.
Input	The first line contains 3 integers N, K and M. The next M line each contains 3 integers x_i, y_i, w_i, representing a road connecting intersection x_i and y_i with length w_i. The intersections are labelled from 0 to N-1.
Output	Output the shotest length. It such walk does not exists, output -1.
Sample Input	3 4 2 0 1 5 1 2 3
Sample Output	14
Hint
Last Modified	2012-06-04 13:52:06
Time Limit	4 seconds
Memory Limit	64 MB
Accepted Solutions	1
Submitted Solutions	2
Difficulty Factor	258