‎Distance Matrix‎ یک گراف ‎$n$‎ راسی، یک ماتریس ‎$n \times n$‎ است که درایه ‎$(i,j)$‎ آن برابر فاصله دو راس ‎$i$‎ام و ‎$j$‎ام آن است. ‎ ‎Distance Matrix‎ یک گراف وزن‌دار همبند ‎$n$‎ راسی که وزن تمام یال‌های آن بیش‌تر یا مساوی $1$‎ است به شما داده شده است. شما باید کم‌ترین ‎$x$‎ را به‌دست بیاورید که مجموع وزن یال‌های گراف متناظر با آن می‌تواند ‎$x$‎ باشد.‎

• در سطر اول ورودی عدد ‎$1 \leq n \leq 50$‎ آمده است.
• در ‎$n$‎ سطر بعدی، در هر سطر ‎$n$‎ عدد آمده است که ماتریس را مشخص می‌کنند.‎
• تمامی اعداد ورودی بین $0$‎ تا ‎$2500$‎ اند.‎

• در صورتی که هیچ گرافی وجود ندارد که ‎Distance Matrix‎ آن برابر ماتریس ورودی باشد در خروجی ‎$-1$‎ چاپ نمایید.
• در غیر این‌صورت ‎$x$‎ را در خروجی چاپ نمایید.‎

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل