This option finds a minimum cost path from a source node to a destination through costed links.

Input

format

The first line specifies the calculation required. It must contain

format costs

Links

Column	Description
1	l for link
2	src node name
3	dst node name
4	cost

Link costs can be negative. In this case an offset cost will be added to every link so that all costs are zero or positive, and subtracted from the total cost of the path displayed. Interpretation of the result when negative costs are present requires care.

start

Column	Description
1	s
2	starting node name

end

Column	Description
1	e
2	node name-1 for paths to all nodes

Example

format costs
l 1 2 1
l 2 3 1
l 2 4 10
l 4 3 1
s 1
e 4

1 -> 2 -> 3 -> 4 ->  Cost is 6