The Spy

Time limit1sMemory limit256 MB

Summary

Given difference constraints on N product scores in 0 to 100, find the smallest possible gap between the highest and lowest score, or -1 if no assignment exists.

Level: Hard8 of 10
Topics: Shortest path, Graph, Binary search, Math
Solved: No attempts yet

Problem

SPARCS Company, whose chairman is Seokju, decided to release $N$ new products. Its $K$ beta testers agreed among themselves and gave every new product an integer score from 0 to 100.

Jihoon, a spy from the rival GoN Company, asked each of the $K$ beta testers one question and got one piece of information about the scores out of each of them. Information comes in three kinds.

1 a b c : (score of product $a$ ) $-$ (score of product $b$ ) $\ge c$
2 a b c : (score of product $a$ ) $-$ (score of product $b$ ) $\le c$
3 a b c : (score of product $a$ ) $-$ (score of product $b$ ) $= c$

Jihoon tried to pin down the best rated product and the worst rated one, but the information does not go that far. Find the smallest possible value of (highest score) $-$ (lowest score) instead.

Input

The first line contains $N$ and $K$ . ( $2 \le N \le 1000$ , $1 \le K \le 3000$ )

Each of the next $K$ lines contains one piece of information Jihoon obtained, in the format above. ( $1 \le a \le N$ , $1 \le b \le N$ , $|c| \le 100$ )

Output

Print the smallest possible value of (highest score) $-$ (lowest score) over all score assignments that satisfy every piece of information and give each product an integer score from 0 to 100. If no such assignment exists, print -1.

Examples2

Example 1
Input
```
3 1
1 2 3 3
```
Expected output
```
3
```
Example 2
Input
```
2 1
3 1 2 0
```
Expected output
```
0
```