somebody-that-i-used-to-know-juneclash
Source: hackerearth
Difficulty: MEDIUM

The link to the Russian translation.

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 ≤ 10^9). 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