Street Deviation
Maratona de Programação da SBC 
Brazil
Timelimit: 6s
Brazil BrazilThe city hall of a great city of Nlogônia began a recovery program of its asphalt streets. In Nlogônia, every street (which can be one-way or two-way) links directly two crossings. By determination of an old real decree, there is always at least one path between any two points of the city.
In the recovery program the streets will be recovered one at a time and, due to that, one street at a time will be closed to traffic. This closure may cause traffic chaos at the venue, violating the royal decree by preventing several citizens from returning home from their works and vice versa. The city hall can convert some of the one-way streets into two-way ones, but it prefers to avoid that because it tends to provoke more severe accidents; the city hall prefers to create deviations by just reversing the ways of the existing one-way streets.
The Nlogônia King asked his servants to write a program that, given the streets description of a city, find if a path continues to exist between any two points of the city (even if it is necessary to change the other streets directions) when a given street is blocked for recovery.
The input consists of several test cases. The first line of a test case contains two integers N (1 ≤ N ≤ 103) and M (1 ≤ M ≤ 105), representing the number of crossings and the number of streets in the city. The crossings are identified by integers from 1 to N and the streets are identified by integer numbers from 1 to M. Each of the M following lines describes one street and contains three integers (1 ≤ A), B (B ≤ N) and T (1 ≤ T ≤ 2), where A and B are the crossings which the street directly links, and T denotes the direction of the street: if T = 1 the street is one-way in the direction from A to B; else if T = 2 the street is two-way. The first described street will be interdicted for recovery.
For each test case your program should print one line containing one character which describes what should the city hall do to respect the royal decree after the street closure for recoveries:
| Sample Input | Sample Output |
|
3 3 |
- |