दंगे और रास्ते

किसी देश में n शहर हैं, जिनको आपस में जोड़ने के लिए m सड़कें मौजूद हैं। प्रत्येक सड़क पर चल रहे दंगों के कारण उसके खुले रहने की एक निश्चित संभावना (0 ≤ ≤ 1) निर्धारित की गई है। शहर स्वयं हमेशा खुले रहते हैं। आपका काम यह है कि शहर 1 से शहर n तक ऐसा रास्ता (path) खोजें, जिसके सभी सड़कें खुले रहने की संयुक्त संभावना अधिकतम हो। यदि शहर 1 से शहर n तक कोई रास्ता मौजूद नहीं है, तो उसकी संभावना 0 मानी जाती है।

एक प्रोग्राम लिखिए जो शहर 1 से शहर n तक किसी रास्ते के खुले रहने की अधिकतम संभावना निकाल सके।

इनपुट

पहली पंक्ति में दो स्पेस से अलग किए गए संख्यात्मक मान n और m दिए जाते हैं (1 ≤ n ≤ 10 000, 1 ≤ m ≤ 20 000), जो क्रमशः शहरों की कुल संख्या और सड़कों की कुल संख्या दर्शाते हैं।

इसके बाद की अगली m पंक्तियों में से प्रत्येक पंक्ति में तीन स्पेस से अलग किए गए मान , , और (1 ≤ ai, bi ≤ n, 0 ≤ pi ≤ 1) दिए जाते हैं। ये मान शहर $$aibipi$$** को दर्शाते हैं।

आउटपुट

आउटपुट में एक वास्तविक संख्या (real number) प्रदर्शित करें, जो शहर 1 से शहर n तक किसी मार्ग के खुले रहने की अधिकतम संभावना को दर्शाती है। यदि आपका उत्तर सही उत्तर से अधिकतम 1e-5 के अंतर तक मेल खाता है, तो उसे स्वीकार कर लिया जाएगा।

उदाहरण