A delivery drone network connects n relay hubs, numbered 0 to n - 1. There are m
one-way relay links; a link from hub u to hub v costs w units of battery to traverse. The drone
always launches from hub 0 and must reach a designated base hub. Multiple links between the same
pair of hubs may exist (with different costs), and a link never connects a hub to itself.
Print the minimum total battery cost to travel from hub 0 to the base hub, moving only along the
directed links. If the base hub cannot be reached from hub 0, print -1 instead.
Input format
Line 1: two integers n m.
Next m lines: three integers u v w -- a directed link from hub u to hub v costing w battery
units (hubs are 0-indexed).
Last line: one integer, the index of the base hub.
Output format
A single integer: the minimum total cost from hub 0 to the base hub, or -1 if it is unreachable.
Constraints
- 1 <= n <= 1000
- 0 <= m <= 4000
- 0 <= u, v < n, u != v
- 1 <= w <= 1000
- 0 <= base hub index < n