#include <iostream>                                                                                                                                                                                         
#include <algorithm>                                                                                                                                                                                        
#include <cstring>                                                                                                                                                                                          
#include <vector>                                                                                                                                                                                           
#include <numeric>                                                                                                                                                                                          
using namespace std;                                                                                                                                                                                        
                                                                                                                                                                                                            
typedef long long ll;                                                                                                                                                                                       
                                                                                                                                                                                                            
int main()                                                                                                                                                                                                  
{                                                                                                                                                                                                           
    ll n;                                                                                                                                                                                                   
                                                                                                                                                                                                            
    cin >>n;                                                                                                                                                                                                
                                                                                                                                                                                                            
    vector<vector<ll> >  d(n, vector<ll>(n));                                                                                                                                                               
                                                                                                                                                                                                            
    for (int i = 0;i<n;++i){                                                                                                                                                                                
        for (int j =0; j<n; ++j) {                                                                                                                                                                          
            ll a;                                                                                                                                                                                           
            cin >> a;                                                                                                                                                                                       
            d[i][j] = a;                                                                                                                                                                                    
        }                                                                                                                                                                                                   
    }                                                                                                                                                                                                       
                                                                                                                                                                                                            
    ll sum = 0;                                                                                                                                                                                             
    for (int i=0;i<n;++i) {                                                                                                                                                                                 
        for(int j=i+1;j<n;++j){                                                                                                                                                                             
            bool via = false;                                                                                                                                                                               
            for(int k=0;k<n;++k){                                                                                                                                                                           
                if (k==i || k==j) continue;                                                                                                                                                                 
                                                                                                                                                                                                            
                if (d[i][j] > d[i][k]+d[k][j]) {                                                                                                                                                            
                    cout << -1 << endl;                                                                                                                                                                     
                    return 0;                                                                                                                                                                               
                } else if (d[i][j] == d[i][k] + d[k][j]) {                                                                                                                                                  
                    via = true;                                                                                                                                                                             
                }                                                                                                                                                                                           
            }                                                                                                                                                                                               
            if (!via) sum += d[i][j];                                                                                                                                                                       
        }                                                                                                                                                                                                   
    }                                                                                                                                                                                                       
                                                                                                                                                                                                            
    cout << sum << endl;                                                                                                                                                                                    
}     

Measured memory_bytes: 1024