Black and White
Tag(s):

Algorithms, DFS, DP, Dijkstra, Graph Representation, Graph Theory, Graphs, Medium

Problem
Editorial
Analytics

You are given a graph $G$ consisting of $N$ nodes and $M$ edges. Each node of $G$ is either colored in black or white. Also, each edge of $G$ has a particular wieight. Now, you need to find the least expensive path between node $1$ and node $N$, such that difference of the number of black nodes and white nodes on the path is no more than $1$.

It is guaranteed $G$ does not consist of multiple edges and self loops.

Input Format:

The first line contains two space separated integers  $N$ and $M$. Each of the next  $M$ lines contains $3$ space separated integers $u,v,l$ which denotes that there is an edge from node $u$ to node $v$ having a weight $l$. The next line contains $N$ space separated integers where each integer is either $0$ or $1$. If the $i^{th}$ integer is $0$ it denotes that $i^{th}$ node is black , otherwise it is white.

Constraints

$1 \le N \le 1000$

$1 \le M \le 10000$

$1 \le l \le 1000$

$1 \le u , v \le N, u \ne v$

Output Format

Output a single integer denoting the length of the optimal path fulfilling the requirements. Print -1 if there is no such path.

SAMPLE INPUT
6 6
1 2 1
2 3 1
1 4 2
4 3 2
3 5 2
5 6 3
1 1 1 0 0 0

SAMPLE OUTPUT
7

Explanation

The optimal path satisfying all the conditions would be :

$1->2->3->5->6$

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), TypeScript, Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...