Pondo Path Queries

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

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

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

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

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