Algoritmo de caminho mais curto Dijkstra com custo de borda

Eu tenho um gráfico ponderado positivo direcionado. Cada aresta tem um custo de uso. Eu tenho apenas um dinheiro, quero calcular os caminhos mais curtos com o algoritmo dijkstra, mas a soma dos custos de bordas na rota deve ser menor ou igual a A.

Quero fazer isso com a menor modificação do Dijstra (se eu puder fazê-lo com a pequena modificação do Dijkstra). Eu devo fazer isso emO(n*log(n)) se eu puder, mas acho que posso.

Alguém pode me ajudar com isso?