You are given an undirected weighted graph with $n$ vertices and $m$ edges.

Consider all shortest paths between vertices $1$ and $n$, for any vertex such as $v\ (1 \le v \le n)$, say that, if $v$ is in either all shortest paths or some of them or none of them.

Input format

• The first line contains two integers $n, m$ denoting the number of the graph's vertices and edges respectively.
• Each of the following $m$ lines contains space-separated $v_i, u_i$, and $w_i$ describing the graph's $i^{th}$ edge's vertices ($v_i, u_i$) and its weight ($w_i$).

Output format

Print $n$ lines where the $i^{th}$ line contains either $all$ if vertex $i$ is in all shortest paths between $1$ to $n$ or $some$ if vertex $i$ is in some of shortest paths or $none$ otherwise.

Constraints

$1 \leq n \leq 2 \times 10^5 \\ 1 \leq m \leq 3 \times 10^5$

$1 \leq v_i, u_i \leq n \\ 1 \leq w_i \leq 10^9$

It is guaranteed that there are no multiple edges or self-loops in the graph.
Also, it is guaranteed that the graph is connected.