The problem asks for single-source shortest paths. Weights are positive. N is large (), so Floyd-Warshall would take operations and time out. BFS will not work because weights vary.
Bellman-Ford would work but runs in , slower than Dijkstra's . Dijkstra is the clear choice. Non-negative weights, single-source, large graph. Use an adjacency list and a min-heap for the implementation.