ट्रैफिक इंटेंसिटी (Traffic Intensity)
यहाँ
n शहर हैं, जो m सड़कों से जुड़े हुए हैं। प्रत्येक सड़क एक परिवहन मार्ग को दर्शाती है और उसके पास एक ट्रैफिक इंटेंसिटी मान होता है, जो उस सड़क पर होने वाले जाम या भीड़भाड़ के स्तर को दर्शाता है।आपका काम है कि प्रत्येक शहर
i के लिए, शहर 1 से शहर i तक जाने पर मिलने वाली न्यूनतम संभव ट्रांज़िट भीड़भाड़ (transit congestion) का पता लगाएँ। किसी पथ की ट्रांज़िट भीड़भाड़ उस पथ पर आने वाली अधिकतम ट्रैफिक इंटेंसिटी के बराबर मानी जाती है।इनपुट
इनपुट की पहली पंक्ति में दो स्पेस-सेपरेटेड पूरे अंक होते हैं,
n और m (), जो क्रमशः शहरों की संख्या और सड़कों की संख्या को दर्शाते हैं।अगली
m पंक्तियों में से प्रत्येक में तीन स्पेस-सेपरेटेड पूर्णांक और () दिए होते हैं, जो इस बात का ब्योरा देते हैं कि शहर और के बीच एक सड़क है और उसकी ट्रैफिक इंटेंसिटी है।आउटपुट
एक ही पंक्ति में
n-1 स्पेस-सेपरेटेड पूर्णांक प्रिंट करें, जहाँ i-वाँ अंक शहर 1 से शहर i+1 तक पहुँचने पर प्राप्त होने वाली न्यूनतम ट्रांज़िट भीड़भाड़ को दर्शाता है।उदाहरण
Input | Output |
5 5
1 2 5
1 3 2
4 5 10
4 3 6
1 5 9 | 5 2 6 9 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB