Построим граф с инвертированными рёбрами и запустим для него алгоритм Дейкстры, вычисляющий в каждой вершине $$$v$$$ минимальную сумму денег $$$d[v]$$$, с которой из этой вершины можно покинуть граф. Множество стартовых вершин — это вершины с выходами, величины $$$d[v]$$$ для них равны $$$c_v$$$, сразу поместим их все в очередь с приоритетами. Далее при каждом переходе по инвертированному ребру из $$$v$$$ в $$$u$$$ будем подбирать такое стартовое значение $$$d[u]$$$, чтобы $$$d[u] - \lfloor \sqrt{d[u]} \rfloor \ge d[v]$$$. В силу монотонности это можно делать бинарным поиском.

Если в качестве очереди с приоритетами использовать C++ set, то общее время работы составляет $$$O(m(\log(n)+\log(max)))$$$, где $$$max$$$ — максимальный ответ в вершине, который в худшем случае не превышает $$$10^{10}$$$. Также эта оценка позволяет заметить, что извлечение квадратного корня при вычислениях можно выполнять с использованием стандартного $$$sqrt()$$$, не прибегая к дополнительным приёмам для повышения точности.