====== Distace Matrix ======
‎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$‎ را در خروجی چاپ نمایید.‎
===== محدودیت‌ها =====


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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|3‎ \\ 0 2 2‎ \\ 2 0 2‎ \\ 2 2 0 | 6 |
|5‎ \\ 0 6 15 2 6‎ \\ 6 0 9 8 12‎ \\ 15 9 0 16 18‎ \\ 2 8 16 0 4‎ \\ ‎6 12 18 4 0 | 55 |
</WRAP>
  * [[سوال ۳۳|سوال بعد]]
  * [[سوال ۳۱|سوال قبل]]