Description

Dijkstra
Input (Standard input)
The number of vertex N is given (1≤N≤5,000) in the first line.
Next two lines are given.
First line of the two lines, index of a vertex(a) and the number of edges E of the vertex(a) are given (1≤E≤N).
In second line, destination vertex(b) from vertex(a) of First line and the weight W of the edge from vertex(a) to vertex(b) are given, resp ectively.
Output (Standard output)
Print the most large weight all shortest-path weight of vertex 1.
[Example]
Input Output
5
12
2 10 35
22
4 1 32
33
2 3 4 9 52
41
54
52
1 7 36 9
Description
1. File name must be Dijkstra.cpp
2. Make a comment of your student ID, name and class in the first line of the source code. ex) 2014601028_Honggildong_A
3. Please keep the source code that you have submitted for some unexpected accident.