नेगसाइकिल। नकारात्मक चक्र
Problem
एक भारित निर्देशित ग्राफ दिया गया है। यह निर्धारित करना आवश्यक है कि इसमें नकारात्मक भार का चक्र है या नहीं। यह गारंटी है कि ग्राफ के सभी कोने पहले से पहुंच योग्य हैं।
इनपुट:
इनपुट फ़ाइल की पहली पंक्ति में दो प्राकृतिक संख्याएं n और m — ग्राफ़ के शीर्षों और किनारों की संख्या क्रमशः ( n ≤ 1 111, m ≤ 11 111)।
अगली m पंक्तियों में किनारों का वर्णन है, प्रति पंक्ति एक। किनारा संख्या i तीन संख्याओं bi, ei और wi — पसली के सिरों की संख्या और उसका वजन क्रमशः (1 ≤ bi, ei ≤ n, −100 000 ≤ wi ≤ 100 000) . ध्यान दें कि ग्राफ़ में कई किनारे और लूप हो सकते हैं।
आउटपुट:
यदि ग्राफ़ में ऋणात्मक भार का चक्र है और नहीं — अन्यथा।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| हां |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| नहीं |