Second shortest path - MarisaOJ: Marisa Online Judge

Given an undirected connected graph with

$n$ vertices and

$m$ edges, find the second shortest path from

$1$ to

$n$ . The length of this path must be greater than the shortest path. ### Input - The first line contains two integers

$n$ and

$m$ . - The next

$m$ lines each contain three integers

$u$ ,

$v$ , and

$w$ , indicating a path of length

$w$ between

$u$ and

$v$ . ### Output - Print an integer representing the length of the second shortest path. ### Constraints -

$1 \le n, m \le 10^5$ . -

$1 \le u, v \le n$ . -

$1 \le w \le 10^4$ . ### Example Input:

$4 4 1 2 100 2 4 200 2 3 250 3 4 100$

Output:

$450$

Topic

Graph

Shortest path

Rating

1400

Solution (0)

Solution