Byteland Trip
Tag(s):

## Algorithms, Binary Search, Floyd Warshall, Medium

Problem
Editorial
Analytics

Chintu is a member of the Lolympics committee and is assigned the task of dropping the players from the one stadium to another. There are total N stadiums in Byteland. There is at least one path between any two stadiums. Each stadium has a Dominos outlet near it. Chintu loves pizza and will not drive the bus until and unless he gets one when he's hungry. A trip from one stadium to another can be completed by buying atmost X pizzas for Chintu. He eats pizza at the beginning of each trip which is also counted as one of the X pizzas. Calculate the total minimum distance that Chintu can cover after eating a single pizza i.e. the distance after which Chintu gets hungry and throws tantrums.

Chintu can buy at most one pizza from one stadium.

Input:
The first line consists of N, X and M denoting the number of stadiums, maximum number of times Chintu can buy pizzas and the number of paths between the stadiums.
The next M lines consists of u,v and w denoting that there is a path from stadium u to stadium v of length w.

Output:
A single integer which is the desired distance.

Constraints:
1 <= N <= 102
1 <= X <= N
N-1 <= M <= 105
1 <= u,v <= N
1 <= w <= 109

SAMPLE INPUT
4 3 4
1 2 10
1 4 40
2 3 20
3 4 30

SAMPLE OUTPUT
30

Explanation

In the sample test case, Chintu can visit any stadium from another stadium after eating atmost 3 pizzas if the minimum distance he can cover after eating a single pizza is greater than or equal to 30.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

October Easy '16

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Sorting
• Math > Number Theory
• Algorithms > Dynamic Programming
• Data Structures > Advanced Data Structures
• Math > Probablity