The hospital's infection control team is mapping worst-case contamination exposure across the building. The building consists of ~n~ rooms connected by ~m~ one-way corridors. Each corridor ~(u,v,w)~ means that a staff member walking from room ~u~ to room ~v~ through this corridor has their contamination risk index change by ~w~: corridors that pass near a contamination source have positive ~w~ (risk increases), while corridors that pass through a decontamination checkpoint have negative ~w~ (risk decreases).

Staff always begin their shift at the decontamination entry, room ~1~, with a risk index of ~0~. Since the corridor layout allows multiple different routes between rooms, a staff member's risk index upon reaching a room depends on which route they took. For safety planning, the team wants to know the worst-case (maximum) risk index achievable at each room, over every possible route from room ~1~.

There is a hazard the team is specifically worried about: if a cycle of corridors reachable from room ~1~ strictly increases total risk every time it is completed, then a staff member could in principle loop through it repeatedly, making their risk index unboundedly large. Any room reachable from such a cycle has no well-defined worst-case risk index and must be flagged.

Input

The first line contains two integers ~n~ and ~m~ ~(1 \leq n \leq 2000, 0 \leq m \leq 4000)~, the number of rooms and the number of corridors.

Each of the next ~m~ lines contains three integers ~u~, ~v~, and ~w~ ~(1 \leq u, v \leq n, u \neq v, -10^9 \leq w \leq 10^9)~, describing a one-way corridor from room ~u~ to room ~v~ that changes risk index by ~w~.

Output

Output ~n~ lines. For each room ~i~, output UNREACHABLE if it cannot be reached from room ~1~, UNSAFE if it is reachable from a risk-increasing cycle that is itself reachable from room ~1~, or its maximum risk index otherwise.

Example

Input 1

5 5
1 2 3
2 3 -1
1 4 2
4 5 -10
3 5 4

Output 1

0
3
2
2
6

Input 2

5 5
1 2 3
2 3 -1
3 2 5
1 4 2
4 5 -10

Output 2

0
UNSAFE
UNSAFE
2
-8

Input 3

3 1
1 2 5

Output 3

0
5
UNREACHABLE