Caminho mais curto com um toque

eu tenhon vértices em arestas ponderadas não direcionadas entre elas (os pesos representam minutos). Cada vértice contém um número de minutos necessários para tomar um café nesse vértice.

Desejo determinar a menor quantidade de tempo (minutos) necessária para obter do vérticev ao vérticew mas com a restrição adicional de que eu tenho que tomar meu café em exatamente um dos vértices a caminho dev paraw)

Exemplo:

(número no vértice é a quantidade de minutos necessária para tomar um café, os pesos nas bordas representam a quantidade de minutos necessários para percorrer essa borda)

Ganharv paraw e beba um café a caminho, produza o tempo mínimo necessário (a saída deve ser 30).

Minha abordagem atual é encontrar o caminho mais curto com o Dijkstra (somar os pesos de todas as arestas desse caminho) e, em seguida, adicionar o valor do vértice com o menor tempo de café nesse caminho ao meu resultado, a fim de obter o tempo total necessário para ganharv paraw.

Minha abordagem não funciona. Aqui está um exemplo em que minha abordagem falha (o resultado da minha abordagem é de 12 minutos, o resultado real deve ser de 6 minutos):

Como determinar a menor quantidade de tempo do vérticev paraw com a restrição de que preciso tomar um café no meu caminho?