Primera Subtarea:

Para esta subtarea podemos hacer exactamente lo que dice el problema, para cada nodo ~u~, corremos un dijkstra, y despues recorremos todos los nodos, denotemos el que estamos recorriendo como ~v~, entonces la respuesta para ~u~, es el mínimo entre lo que teníamos antes o ~2 * dist(u,v) + a[v]~. La complejidad total es ~O(n m \log{m})~.

Segunda subtarea:

La idea principal es correr todo en un solo dijkstra, podemos crear un nodo auxiliar, y conectarlo con cada nodo ~u~ con costo ~a[u]~, despues añadimos las otras aristas del grafo multiplicadas por 2 (ya que hay que ir y virar), la distancia del nodo auxiliar a cada uno de los demás nodos es la respuesta del problema.

No es necesario añadir este nodo explicitamente, simplemente se puede empezar el dijkstra con todos los nodos en la cola de prioridad, y con ~dist[u]~ inicializado en ~a[u]~ y ya es suficiente.

Complejidad ~O((n+m)logn)~