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

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