409475: GYM103577 A Artistic Swimming

Tomi is participating in a Dog's artistic swimming contest. This is a very special competition, because dogs know how to swim very well. They have to move between different designated points in a pool (they must move between pairs of designated points, not to or from other place), in the minimum amount of time. However, there is a twist. The jury will ask every participant to wait for $$$x$$$ seconds on each designated point in the pool before they can move to the next one, and also wait $$$x$$$ seconds in the final designated point to finish the race.

Tomi and his coach Diego know Tomi's abilities really well, they know exactly how many seconds it takes for Tomi to swim from one designated point to another (Tomi might not be able to swim directly from one designated point to another). Tomi and Diego are resting today, so they need your help to simulate a few scenarios and determine how many seconds does it take for Tomi to go from a given designated point to another, while waiting $$$x$$$ seconds on each designated point. The referee (Osman) is unpredictable, and is uncertain what value of $$$x$$$ he will use in the competition.

The first line will contain three integers $$$n, m, q$$$ ($$$2 \leq n \leq 500$$$, $$$1 \leq m \leq 2n$$$ and $$$1 \leq q \leq 10^5$$$) which represent the number of designated points, the number of Tomi's times Diego knows and the number of queries, respectively. Next, there will be $$$m$$$ lines with three integers each: $$$u$$$, $$$v$$$ and $$$w$$$ ($$$1 \leq u, v \leq n$$$ and $$$1 \leq w \leq 500$$$), which represents that Tomi swims from designated point $$$u$$$ to designated point $$$v$$$ in $$$w$$$ seconds. You are guaranteed that every ordered pair $$$(u, v)$$$ will be different. Finally, there will be $$$q$$$ lines, each line will have 3 integers $$$u$$$, $$$v$$$ and $$$x$$$, which represent a query to find the time to go from designated point $$$u$$$ to designated point $$$v$$$ waiting $$$x$$$ ($$$0 \leq x \leq 50000$$$) seconds on each node.

For each query, print in a single line the minimum number of seconds it will take Tomi to go from $$$u$$$ to $$$v$$$. If there is no way to go from $$$u$$$ to $$$v$$$, print -1.

4 6 3
1 4 1
1 2 8
4 3 9
2 3 1
4 2 2
3 1 4
1 3 0
1 3 10
2 1 1

4
39
8

2 1 3
1 2 100
1 1 100
2 2 100
1 2 100

100
100
300