Double edge - MarisaOJ: Marisa Online Judge

Given an undirected, weighted graph of

n

$n$ vertices and

m

$m$ edges. You can only traverse 2 edges at a time (i.e. from

a

$a$ to

b

$b$ to

c

$c$ ) and cost you

w_{a b} \times w_{b c}

$w_{ab}\times w_{bc}$ . Find the minimum cost to travel 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

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

33121232133

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

Output:

2

$2$

Topic

Graph

Shortest path

Rating

1300

Solution (1)

Solution