Came up with a graph problem I can't solve: looking for ideas

This is a problem I came up with while thinking about cycle-based optimization on graphs. I'm not sure if it's well-known or if I'm missing something obvious, either way I couldn't solve it, so I'd love to hear how more experienced people would approach it.

Problem Statement

You are given a directed graph with N nodes and M edges. It may have self-loops and multiple edges between the same pair of nodes.

Each edge is described by three integers u, v, w:

you can move from node u to node v
the move takes exactly 1 unit of time
you gain w coins after using this edge

You start at node 1 with 0 coins. You may traverse any edge any number of times and revisit nodes freely.

Find the minimum time to collect at least K coins. If it is impossible, print -1.

Examples

Example 1

Input:
5 6 24
1 2 6
2 1 6
1 3 0
3 4 8
4 5 8
5 3 7

Output:
4

Explanation

Example 2

Input:
5 6 31
1 2 6
2 1 6
1 3 0
3 4 8
4 5 8
5 3 7

Output:
5

Explanation

Constraints

$$$1 \le N, M \le 2 \cdot 10^5$$$

$$$1 \le K \le 10^{18}$$$

$$$w \ge 0$$$

Why I Find This Hard

The tricky part is that the best strategy is not fixed, it depends on K:

Some cycles have great coins/move ratio but are expensive to reach
Others are easy to enter but scale worse
K can be up to $$$10^{18}$$$ , so any DP over coins is completely out

My rough instinct says it involves some mix of:

SCC condensation: collapsing strongly connected components
Cycle profit analysis: finding the highest coins-per-time ratio cycle reachable from node 1
Shortest-path reasoning: accounting for the "entry cost" to reach each cycle
Binary search on time: fix T, ask if we can collect K coins in T steps

But I can't figure out how to tie these together cleanly, especially when multiple cycles compete and the answer shifts with K.