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$ را در خروجی چاپ نمایید.

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