Pondo Path Queries

Problem Statement

You are given a directed graph with ~n~ vertices and ~m~ edges with weights. You are also given ~Q~ queries each containing three integers ~u~, ~v~ and ~k~. For each query determine the shortest walk from ~u~ to ~v~ using at most ~k~ edges. NOTE: A walk is like a path but can repeat vertices.

Input Format

Your first line will contain three space-separated integers ~n~, ~m~ and ~Q~. Your next ~m~ lines will contain three integers each ~u~, ~v~ and ~w~ representing and edge from ~u~ to ~v~ with weight ~w~. Your next ~Q~ lines will contain three integers each ~u~, ~v~ and ~k~ representing the start point, end point and max number of edges respectively.

Output Format

You should output one line for each query, representing the minimum distance from ~u~ to ~v~ after a walk of at most ~k~ in length. If it is not possible to reach in ~k~ edges or less, then output NOT POSSIBLE.

Constraints

• ~1 \leq n, u, v \leq 100~
• ~1 \leq m \leq n \cdot (n - 1)~
• ~-100 \leq w \leq 100~
• ~1 \leq k \leq 10^9~

YOU CAN HAVE EDGES BETWEEN THE SAME NODES

Sample Cases

Input 1

5 4 10
1 2 1
2 3 2 
3 4 -2 
4 5 3
1 2 0
1 2 10
1 3 1
1 3 2
1 5 4
5 5 4
5 4 4
5 3 4
5 2 4
5 1 4

Output 1

NOT POSSIBLE
1
NOT POSSIBLE
3
4
0
NOT POSSIBLE
NOT POSSIBLE
NOT POSSIBLE
NOT POSSIBLE

Input 2

2 2 10
1 2 1
2 1 -2
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10

Output 2

0
-1
-1
-2
-2
-3
-3
-4
-4
-5

Template

n, m, q = map(int, input().split())
edges = [None] * m
for i in range(m):
    u, v, w = map(int, input().spilt())
    edges[i] = (u, v, w)

# print your output