Module: क्रमपरिवर्तन पर पुनरावृति

Problem

महामहिम राजा बुबेई द्वितीय अपने डोमेन के चारों ओर यात्रा करना चाहते थे। उसी समय, मार्ग की निम्नलिखित इच्छाएँ हैं:

1) मार्ग को कम से कम समय लेना चाहिए (शाही समय - एक बहुत ही मूल्यवान चीज है और इसे संरक्षित किया जाना चाहिए);

2) मार्ग में सभी बस्तियाँ ठीक एक बार शामिल होनी चाहिए (यदि राजा किसी बस्ती को याद करता है, तो उसके निवासी शाही असावधानी से नाराज होंगे और कर देना बंद कर देंगे; यदि राजा एक से अधिक बार किसी बस्ती का दौरा करता है, तो शेष के निवासी सेटलमेंट आइटम भी नाराज़ होंगे)

3) मार्ग को राज्य की राजधानी में शुरू और समाप्त होना चाहिए (अपनी संपत्ति के आसपास यात्रा करने के बाद, राजा को तुरंत व्यवसाय में उतरना चाहिए)। पूंजी को मार्ग में ठीक 2 बार शामिल किया गया है: प्रस्थान के बिंदु के रूप में और गंतव्य के रूप में, यह मार्ग का मध्यवर्ती बंदोबस्त नहीं हो सकता।

एक प्रोग्राम लिखें जो इस तरह के मार्ग को खोजने के लिए राज्य के रोड मैप का उपयोग करता है या यह निर्धारित करता है कि सभी आवश्यकताओं को पूरा करना असंभव है।

इनपुट
पहले संख्या N दर्ज करें (प्राकृतिक, 10 से अधिक नहीं) – राज्य में बस्तियों की संख्या। फिर प्रत्येक – में N संख्याओं की N पंक्तियों का अनुसरण करता है। बस्तियों के बीच यात्रा का समय (समय - एक गैर-ऋणात्मक पूर्णांक है, 500 से अधिक नहीं है; यदि समय = 0 है, तो इसका मतलब है कि कुछ बस्तियों के बीच कोई रास्ता नहीं है)। बस्ती नंबर 1 राज्य की राजधानी है।

छाप
कम से कम कुल समय प्रिंट करें जो महामहिम अपने डोमेन के चारों ओर एक चक्कर लगाने में खर्च करेंगे, या नंबर -1 अगर दी गई संपत्तियों के साथ मार्ग बनाना असंभव है।

उदाहरण

<टेबल क्लास = "टेबल-एसएम टेबल-बॉर्डर टेबल-स्ट्राइप्ड टेबल-लिस्ट-टेस्ट"> <सिर> <थ वर्ग = "अंक"> # <वें>इनपुट <वें>आउटपुट <शरीर> 1 1
0 0 2 2
0 1
10 2 3 2
0 85 
85 0  170