Somebody That I Used to Know
Tag(s):

## Graph Theory, Medium, Shortest-path

Problem
Editorial
Analytics

On the way to kill one of vampires Reyna addressed, Damon and Enzo arrive at a mysterious town. This town has n intersections and m one-way roads. Each road has a length and a character written on it! This character is either a '(' or ')'.

This town is mysterious because in it, a route (may pass a road more than once) is proper (one can kill vampires at the end of it) iff when we write down the characters on the roads one by one, it forms a correct bracket sequence.

A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence

Damon and Enzo want to know for each two intersections s and t, the length of the shortest proper route from s to t (It may not exist, also for s = t answer is 0 since "" is a correct bracket sequence due to the definition).

They are really pissed off right now, so you better answer them ;)

### Input

The first line of input contains two integers n and m (1 ≤ n ≤ 300, 1 ≤ m ≤ min(80000, n×(n-1))).

The next m lines contain the roads. Each line contains three integers v, u, w and a character c (either ( or )) meaning there is a road from *v to u with length w written c on it (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ w ≤ 109). It's guaranteed that there is at most one road from v to u.

### Output

Your output should be a n by n matrix (numbers in each line should be space-separated). j-th cell in i-th row should contain the length of the shortest proper route from i to j if there exists such route, or -1 otherwise.

SAMPLE INPUT
8 10
3 8 2 )
8 6 8 )
4 6 2 )
2 8 9 (
5 1 4 (
3 4 5 (
4 5 6 )
5 4 6 )
3 1 3 )
7 1 9 )

SAMPLE OUTPUT
0 -1 -1 -1 -1 -1 -1 -1
-1 0 -1 -1 -1 17 -1 -1
-1 -1 0 -1 11 7 -1 -1
-1 -1 -1 0 -1 -1 -1 -1
-1 -1 -1 -1 0 -1 -1 -1
-1 -1 -1 -1 -1 0 -1 -1
-1 -1 -1 -1 -1 -1 0 -1
-1 -1 -1 -1 -1 -1 -1 0

Time Limit: 2.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: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), 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...
Your Rating:

## This Problem was Asked in

Challenge Name

June Clash '16

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
Notifications

?