Year 3007, the energy shortage on earth reaches the state of global emergency. United Nation calls a meeting to discuss the feasibility of a proposed space battery-shuttle (SBS) project, and you are invited to the meeting for your expertise on programming. A space battery-shuttle is a space shuttle as well as a huge battery, it can collect solar energy and other form of energy in the universe. An SBS tour always starts from earth, goes through many space stations and comes back to earth. An SBS tour needs energy to complete and at the same time the SBS can collect energy during the tour. An SBS tour is worthy if the energy collected during the tour is more than the energy needed to complete the tour. Therefore, it becomes a holy grail to find a worthy tour. The competition is furious and many countries have carefully studied the net energy consumed from one space station to another by an SBS. A typical measurement is (s1, s2, δ), where s1 denotes the starting space station, s2 denotes the destination space station, and the integer δ (−100 ≤ δ ≤ 100) denotes the net energy consumed from s1 to s2 , when δ is positive it means that the energy collected is less than the energy needed to reach s2 from s1, and when δ is negative it means that the energy collected from s1 to s2 is more than the energy consumed. Each country has her own collection of measurements, called route map, from space stations to space stations and due to the potential profit involved all countries carry out independent studies. Each country covers at most n (2 ≤ n ≤ 60) space stations and study at most m (1 ≤ m ≤ 3540) measurements. We use 0 to denote earth and each space stations are numbered from 1 to n if n space stations appeared in the map. Given a set of route maps, your task is to check each route map and decide if it contains a worthy tour. (A tour is a sequence of space stations, 0, s1 , s2 , ..., sk , 0, such that a voyager will bring energy home from the earth to s1 then following the sequence and back to earth from sk . Please note that a space station can appear in the sequence many times. And the SBS can go from some space station si to another space station sj many times in a tour.) Also it is a known fact that from earth to any space station needs 40 units of energy and vice versa, i,e, δ0,i = δi,0 = 40, ∀1 ≤ i ≤ n, where δi,j denotes the net energy consumed from space station i to space station j.
The first line of the input file contains an integer indicating the number of test cases to follow. For each test case, the first line contains two integers, n and m separated by a space. Followed by m lines of measurements, each measurement consists of three integers, s1 , s2 , and δ, separated by space.
For each test case, output 1 if there is a worthy tour, otherwise output 0.
3 2 1 1 2 -90 2 1 1 2 -60 2 2 1 2 -5 2 1 -5
1 0 1
Migrated from old NTUJ.
NCPC2007
| No. | Testdata Range | Score |
|---|