एन और पाई महोत्सव
Problem
आज, ऐस्ने कैसल एक पाई उत्सव की मेजबानी कर रहा है जिसमें n बेकरियां भाग लेती हैं, जिनमें से प्रत्येक की अपनी अनूठी संख्या 1 से n तक होती है।
कुछ बेकरियां दो-तरफ़ा सड़कों से जुड़ी हुई हैं, लेकिन इस तरह से कि अगर बेकरी i से बेकरी j तक चलना संभव हो, तो उनके बीच बिल्कुल एक ही रास्ता है।
जब एन i-th बेकरी में पाई खाता है, तो उसे अi सुख मिलता है। और अगर यह कुछ v और u नंबर वाली बेकरियों के बीच से गुजरती है, तो पाई की स्वादिष्ट सुगंध Cv,u आनंद लाती है।
एन हर बेकरी में एक से अधिक बार नहीं जाना चाहती (कुछ तो बिल्कुल भी नहीं जा सकती हैं), लेकिन वह त्योहार का अधिक से अधिक लाभ उठाना चाहती है।
वह किसी एक बेकरी से शुरू करेगा और केवल मौजूदा सड़कों का उपयोग करके उनके बीच से गुजरेगा।
अधिकतम संभव आनंद निर्धारित करने में एन की मदद करें।
इनपुट:
पहली पंक्ति में संख्या n (1 <= n <= 50000) - बेकरी की संख्या, और संख्या k - बेकरी के बीच मौजूदा सड़कों की संख्या शामिल है।
दूसरी पंक्ति में n संख्याएँ Ai (0 <= Ai <= 10000) हैं - i-th बेकरी में पाई का आनंद।
फिर k लाइनें आती हैं, प्रत्येक में 3 नंबर v, u, C (1 <= v, u <= n; v ≠ u; 0 <= C <= 10000) होते हैं, जिसका अर्थ है कि बीच में एक सड़क है v और u क्रमांकित बेकरी, और इस सड़क पर सुगंध सी आनंद लाती है।
आउटपुट:
एक नंबर प्रिंट करें - अधिकतम संभव संतुष्टि।
उदाहरण:
<तालिका सीमा = "1" सेलपैडिंग = "1" सेलस्पेसिंग = "1" शैली = "चौड़ाई: 500 पीएक्स;">
<शरीर>
| इनपुट |
आउटपुट |
2 1
1 1
1 2 1
| 3 |
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
| 37 |
स्पष्टीकरण:
पहले उदाहरण में, आपको पहली बेकरी (1 ट्रीट) से शुरुआत करनी होगी, पहली और दूसरी बेकरी (1 ट्रीट) के बीच सड़क पर चलना होगा और दूसरी बेकरी (1 ट्रीट) पर जाना होगा। कुल आनंद - 1+1+1 = 3.
दूसरे उदाहरण में, आपको 5वीं बेकरी (10 खुशी) से शुरुआत करनी होगी, 5वीं और चौथी बेकरी (1 खुशी) के बीच सड़क पर चलना होगा, चौथी बेकरी (6 खुशी) पर जाना होगा, चौथी और दूसरी के बीच की सड़क का अनुसरण करना होगा बेकरी (1 ट्रीट), दूसरी बेकरी (5 ट्रीट) पर जाएँ, दूसरी और तीसरी बेकरी के बीच सड़क पर चलें (10 ट्रीट), तीसरी बेकरी जाएँ (4 ट्रीट)। कुल सुख - 10+1+6+1+5+10+4 = 37।