Minimum Cost Path

Interview

Time limit0.5sMemory limit128 MB

Summary
Given a directed weighted graph of cities and bus routes, compute the minimum cost path from a start city to a destination city.
Level

Medium4 of 10

Topics
Shortest path, Graph, Heap
Solved
No attempts yet

Problem

There are N cities and M directed bus routes. Each bus route has a cost for traveling from one city to another.

Given a start city A and a destination city B, find the minimum total cost needed to travel from A to B. City numbers are from 1 to N.

Input

The first line contains the number of cities N (1 <= N <= 1,000). The second line contains the number of bus routes M (1 <= M <= 100,000).

Each of the next M lines contains one bus route in the form start_city destination_city cost. The cost is an integer greater than or equal to 0 and less than 100,000.

The last line contains the start city and destination city for the query. The input is guaranteed to describe a case where the destination is reachable from the start city.

Output

Print one line containing the minimum cost needed to travel from the start city to the destination city.

Examples1

  1. Example 1

    Input
    5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5
    Expected output
    4