Bye bye maximum edge - MarisaOJ: Marisa Online Judge

Given an undirected, weighted graph of

n

$n$ vertices and

m

$m$ edges. If your path from

u

$u$ to

v

$v$ consists of

k

$k$ edges weigh

w_{1}, w_{2}, . . ., w_{k}

$w_1,w_2,...,w_k$ , then the final weight of the path is calculated as follow:

w_{1} + w_{2} + . . . + w_{k} - m a x (w_{1}, w_{2}, . . ., w_{k})

$w_1+w_2+...+w_k-max(w_1,w_2,...,w_k)$ Find the weight of the shortest path from

1

$1$ to

n

$n$ . ### Input - The first line contains 2 integers

n, m

$n, m$ . - The next

m

$m$ lines, each line contains 3 integers

u, v, w

$u, v, w$ , there is an edge of weight

w

$w$ connecting

u, v

$u, v$ . ### Output - Print the weight of the shortest path from

1

$1$ to

n

$n$ , or print

- 1

$-1$ if no path exists. ### Constraints -

1 \leq n, m \leq 2 \times 10^{5}

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

1 \leq u, v \leq n

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

1 \leq w \leq 10^{9}

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

33121232133

$3 3 1 2 1 2 3 2 1 3 3$

Output:

0

$0$

Topic

Graph

Shortest path

Greedy

Rating

1500

Solution (0)

Solution