/*
Foarte multi concurenti au incercat sa rezolve aceasta problema folosind algoritmul Dijkstra cu heap-uri sau cu arbori de intervale. 
Aceasta solutie ar fi obtinut de la 70 pana la 100 de puncte (in cazul in care se optimiza algoritmul). 
O alta metoda de a obtine 100 de puncte ar fi fost folosirea algoritmul Bellman Ford cu coada (vezi OJI 2004, problema Lanterna).

Solutia oficiala (care este de fapt si cea mai simpla si cea mai usor de implementat) are complexitate O(N+M) ca timp si O(N) ca memorie. 
Ea poate fi dedusa din modul de functionare a algoritmilor Dijkstra sau Bellman Ford. 
Asadar, conditile suficiente si necesare ca distantele minime date sa fie corecte sunt:

-> DS = 0
-> Dx + cost(x, y) ≥ Dy pentru orice muchie (x, y)
-> exista pentru fiecare y (diferit de S) un x astfel incat Dx + cost(x, y) = Dy
Studiati modul in care functioneaza Dijkstra sau Bellman Ford si veti vedea ca logica acestor conditii devine evidenta. 
Verificarea acestor conditii se poate face in complexitatea mentionata mai sus.
*/
#include <cstdio>
using namespace std;
int main()
{
 return 0;
}