Festival 3 - MarisaOJ: Marisa Online Judge

Today is the joyous Tanabata day, and Reimu is preparing to host a festival at Hakurei Shrine. Excited to join in the festivities, Marisa decides to make the day even more memorable by purchasing a sake bottle as a special gift. There are a total of

n

$n$ unique places where Marisa can buy sake, each with its own price denoted by

c_{i}

$c_i$ . To navigate between these places, Marisa can utilize a special two-way transportation system operated by the Kappa. However, there are certain costs associated with using each route. The first time Marisa uses route

i

$i$ , it incurs a cost of

w_{i}

$w_i$ . However, due to the system's unique rules, subsequent uses of the same route will be free. Marisa devises a plan to begin her journey from her house at location

1

$1$ , explore different places to find the perfect sake, and ultimately reach the Hakurei Shrine located at location

n

$n$ . The goal is to determine the minimum cost for Marisa to accomplish her plan and fully enjoy the Tanabata festival. ### Input - The first line contains two integer

n, m

$n,m$ . - The second line contains

n

$n$ integer

c_{i}

$c_i$ . - The next

m

$m$ lines, each line contains three integer

u, v, w

$u,v,w$ , there is a route between

u

$u$ and

v

$v$ and costs

w_{i}

$w_i$ for the first time. ### Output - Print an integer, the minimum cost. ### Constraints -

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

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

1 \leq u, v \leq n, u \neq v

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

1 \leq w_{i}, c_{i} \leq 10^{9}

$1 \le w_i,c_i \le 10^9$ . ### Example Input:

56101011010122231341452151252

$5 6 10 10 1 10 10 1 2 2 2 3 1 3 4 1 4 5 2 1 5 1 2 5 2$

Output:

5

$5$

Shortest path
	Shortest path
	Delete edge
	3D path
	Number of shortest paths
	Double edge
	Second shortest path
	Bye bye maximum edge
	Boardgame
	Teleport
	?
	Math
	Festival 3
	Arbitrage
	Festival 4
	String construction
	Elevator
	Fortress defense

Topic

Graph

Shortest path

Rating

1700

Solution (0)

Solution