219. Synchrograph

time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



In the theory of processes a special case of Petri nets is often considered, called synchrographs. Synchrograph can be represented as directed graph, each arc of which is marked with some non-negative integer number. The vertex of synchrograph is called active if all arcs incoming into this vertex are marked with the positive number.

Synchrograph operates in cycles. Each cycle one active vertex is nondeterministically selected and fired. The vertex fires the following way: the number on each arc incoming into this vertex is decreased by one, and the number on each arc outgoing from this vertex is increased by one. After that the set of active vertices is refreshed due to the new marks of the arcs and the next cycle takes place.

The vertex of synchrograph is called potentially alive if there is the sequence of fires, such that after it the vertex itself fires. The vertex is called alive if after any valid sequence of fires it is potentially alive.

For each vertex of synchrograph detect whether it is alive.

Input

The first line of the input file contains N and M — the number of vertices and arcs of synchrograph respectively (1 ≤ N ≤ 1000, 1 ≤ M ≤ 50000). Next M lines contain arc descriptions --- the beginning of the arc, the end of the arc and the number that this arc is initially marked with. No mark exceeds 109.

Output

For each vertex print 1 if it is alive and 0 in the other case.

Sample test(s)

Input
6 8 
1 2 1 
4 3 0 
2 4 0 
4 3 1 
1 6 0 
6 3 1 
3 2 0 
4 5 1000000000 
 

Output
1 
0 
0 
0 
0 
1 
 

Note
11.12.2003. Clarification done: "For each vertex of synchrograph detect whether it is potentially alive" changed to "For each vertex of synchrograph detect whether it is alive". 
 
  
  
Author:Andrew Stankevich 
Resource:Summer Trainings 2003, Maloyaroslavets 
Date:2003-06-26