stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define Would

#define you

#define please







int main() {

	cin.tie(0);

	ios::sync_with_stdio(false);



	

	int N;

	cin >> N;



	int A[301][301];

	rep1(i, N) {

		rep1(ii, N) {

			cin >> A[i][ii];

		}

	}



	int shouryaku[301][301] = {};

	rep1(k, N) {

		rep1(i, N) {

			rep1(j, N) {

				if (A[i][j] > A[i][k] + A[k][j]) {

					co(-1);

					Would you please return 0;

					//アホか！

				}

				else if (A[i][j] == A[i][k] + A[k][j] && i != k && j != k) {

					shouryaku[i][j] = 1;

				}

			}

		}

	}



	ll goukei = 0;

	rep1(i, N) {

		rep1(ii, N) {

			if(shouryaku[i][ii] == 0) goukei += A[i][ii];

		}

	}



	co(goukei / 2);



	Would you please return 0;

}

// Faster C++ solution for the same problem (measured speedup: 2.497198443363835x):
//#include<bits/stdc++.h>

#include<cstdio>



using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 0; i < (n); i++)

#define rep1(i, n) for(int i = 1; i <= (n); i++)

#define co(x) cout << (x) << "\n"

#define cosp(x) cout << (x) << " "

#define ce(x) cerr << (x) << "\n"

#define cesp(x) cerr << (x) << " "

#define pb push_back

#define mp make_pair

#define Would

#define you

#define please



const int cm = 1 << 17;

char cn[cm], * ci = cn + cm, ct;

inline char getcha() {

	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }

	return *ci++;

}

inline int getint() {

	int A = 0;

	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';

	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';

	return A;

}





int main() {

	//cin.tie(0);

	//ios::sync_with_stdio(false);





	int N = getint();



	int A[301][301];

	rep1(i, N) {

		rep1(ii, N) {

			A[i][ii] = getint();

		}

	}



	int shouryaku[301][301] = {};

	rep1(k, N) {

		rep1(i, N) {

			if (k == i) continue;

			rep1(j, i - 1) {

				if (k == j) continue;

				if (A[i][j] > A[i][k] + A[k][j]) {

					printf("-1");

					return 0;

				}

				else if (A[i][j] == A[i][k] + A[k][j]) {

					shouryaku[i][j] = 1;

				}

			}

		}

	}



	ll goukei = 0;

	rep1(i, N) {

		rep1(ii, i - 1) {

			if (shouryaku[i][ii] == 0) goukei += A[i][ii];

		}

	}



	printf("%lld", goukei);



	Would you please return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define REP(i, n) for(int i = 0; i < n; i++)

#define REPR(i, n) for(int i = n; i >= 0; i--)

#define FOR(i, m, n) for(int i = m; i < n; i++)

#define ALL(obj) (obj).begin(), (obj).end()

#define INF 1e12

typedef long long ll;



int N;

vector<vector<bool>> A(300, vector<bool>(300,true));

vector<vector<ll>> dp(300, vector<ll>(300,INF));



int main() {

    cin >> N;



    REP(i,N){

        REP(j,N){

            cin >> dp[i][j];

        }

    }



    REP(i,N){

        REP(j,N){

            REP(k,N){

                if (j==k || k==i || i==j) continue;

                if (dp[j][k] > dp[j][i] + dp[i][k]){

                    cout << -1 << endl;

                    return 0;

                }else if (dp[j][k] == dp[j][i] + dp[i][k]){

                    A[j][k] = false;

                }

            }

        }

    }



    ll ans = 0;



     REP(i,N){

        REP(j,N){

            if (A[i][j]) ans += dp[i][j];

        }

    }



    cout << ans/2 << endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.8168557398755503x):
#include <bits/stdc++.h>

using namespace std;



#define REP(i, n) for(int i = 0; i < n; i++)

#define REPR(i, n) for(int i = n; i >= 0; i--)

#define FOR(i, m, n) for(int i = m; i < n; i++)

#define ALL(obj) (obj).begin(), (obj).end()

#define INF 1e9

typedef long long ll;





int main() {

    int N; cin >> N;

    vector<vector<pair<int,int>>> A(N, vector<pair<int,int>>(N));

    REP(i,N){

        REP(j,N){

            int a; cin >> a;

            A[i][j] = {a,0};

        }

    }



    REP(i,N-1){

        FOR(j,i+1,N){

            REP(k,N){

                if(i==k || j==k) continue;

                if(A[i][k].first+A[k][j].first < A[i][j].first){

                    cout << -1 << endl;

                    return 0;

                }else if(A[i][k].first+A[k][j].first == A[i][j].first){

                    A[i][j].second = 1;

                }

            }

        }

    }



    ll ans = 0;

    REP(i,N-1){

        FOR(j,i+1,N){

            if(A[i][j].second==0) ans += A[i][j].first;

        }

    }

    cout << ans << endl;

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include<bits/stdc++.h>

using namespace std;

long long int a[1000][1000],b[1000][1000],c[1000][1000];

//char x[1050][150],y[100050][20];



int main()

{

    long long int i,n,m,j,k,x,y;

    long long  int sum=0;

    scanf("%lld",&n);

    //memset(b,1,sizeof(b));

    for(i=1; i<=n; i++)

    {

        for(j=1; j<=n; j++)

        {

            scanf("%lld",&a[i][j]);



        }

    }

    memset(c,0,sizeof(c));

    for(k=1;k<=n;k++)

    {

        for(i=1;i<=n;i++)

        {

            for(j=1;j<=n;j++)

            {

                if(b[i][j]==0)

                {

                    b[i][j]=a[i][j];

                }

                b[i][j]=min(b[i][j],a[i][k]+a[k][j]);

                if((a[i][j]>=a[i][k]+a[k][j])&&(i!=k&&j!=k))

                {

                    c[i][j]=1;

                    b[i][j]=a[i][k]+a[k][j];

                }

            }

        }

    }

    int f=0;

    for(i=1;i<n;i++)

    {

        for(j=i+1;j<=n;j++)

        {

            if(a[i][j]!=b[i][j])

            {

                f=-1;

                break;

            }if((c[i][j]!=1)&&(a[i][j]==b[i][j]))

            {

                sum+=b[i][j];

            }

        }

        if(f==-1)

        {

            break;

        }

    }

    if(f==-1)

    {

        printf("-1");

    }else

    {

        printf("%lld",sum);

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 47.51490371179653x):
#include<stdio.h>



int main()

{

    int a[309][309], n;

    while(~scanf("%d", &n))

    {

        for(int i = 1; i <= n; i++)

            for(int j = 1; j <= n; j++)

                scanf("%d", &a[i][j]);

        long long ans = 0;

        for(int i = 1; i <= n; i++)

        {

            for(int j = 1; j < i; j++)

            {

                bool flag = 1;

                for(int k = 1; k <= n; k++)

                {

                    if(a[i][j] > a[i][k] + a[k][j])

                    {

                        printf("-1\n");

                        return 0;

                    }

                    else if(i != k && k != j && a[i][j] == a[i][k] + a[k][j])

                        flag = 0;

                }

                if(flag)

                    ans += a[i][j];

            }

        }

        printf("%lld\n", ans);

    }

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include<bits/stdc++.h>

using namespace std;

long long int a[1000][1000],b[1000][1000],c[1000][1000];

//char x[1050][150],y[100050][20];



int main()

{

    long long int i,n,m,j,k,x,y;

    long long  int sum=0;

    scanf("%lld",&n);

    //memset(b,1,sizeof(b));

    for(i=1; i<=n; i++)

    {

        for(j=1; j<=n; j++)

        {

            scanf("%lld",&a[i][j]);



        }

    }

    memset(c,0,sizeof(c));

    for(k=1;k<=n;k++)

    {

        for(i=1;i<=n;i++)

        {

            for(j=1;j<=n;j++)

            {

                if(b[i][j]==0)

                {

                    b[i][j]=a[i][j];

                }

                b[i][j]=min(b[i][j],a[i][k]+a[k][j]);

                if((a[i][j]>=a[i][k]+a[k][j])&&(i!=k&&j!=k))

                {

                    c[i][j]=1;

                    b[i][j]=a[i][k]+a[k][j];

                }

            }

        }

    }

    int f=0;

    for(i=1;i<n;i++)

    {

        for(j=i+1;j<=n;j++)

        {

            if(a[i][j]!=b[i][j])

            {

                f=-1;

                break;

            }if((c[i][j]!=1)&&(a[i][j]==b[i][j]))

            {

                sum+=b[i][j];

            }

        }

        if(f==-1)

        {

            break;

        }

    }

    if(f==-1)

    {

        printf("-1");

    }else

    {

        printf("%lld",sum);

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 9.42255330471864x):
#include<bits/stdc++.h>

#define LL long long

using namespace std;

LL n,ans,a[301][301];

bool p[301][301];

int main(){

	cin>>n;

	for(LL i=1;i<=n;i++)

		for(LL j=1;j<=n;j++)cin>>a[i][j];

	for(LL k=1;k<=n;k++)

		for(LL i=1;i<=n;i++)

			for(LL j=1;j<=n;j++)

				if(k!=j&&k!=i&&i!=j){

					if(a[i][j]==a[i][k]+a[k][j])p[i][j]=1;

					if(a[i][j]>a[i][k]+a[k][j])puts("-1"),exit(0);

				}

	for(LL i=1;i<=n;i++)

		for(LL j=1;j<=n;j++)

			if(!p[i][j])ans+=a[i][j];

	printf("%lld\n",ans/2),exit(0);

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f;

long long a,b,v,i,n,m,k,l,an[100010],ans=0,vis[10000],j;

long long ma[600][600],dist[6000],S,vis2[610][610],vis3[6000];

int flag=0;

void dijkstra(long long x)

{//printf("ok\n");

    for(i=1; i<=n; i++)

        dist[i]=(i==x)?0:INF;

    memset(vis,0,sizeof(vis));

   memset(vis3,0,sizeof(vis3));

    for(i=1; i<=n; i++)

    {

        int mark=-1,mindis=INF;

        for(j=1; j<=n; j++)

        {

            if(!vis[j]&&dist[j]<mindis)

            {

                mindis=dist[j];

                mark=j;

            }

        }

        vis[mark]=1;

        for(int j=1; j<=n; j++)

        {

            if(!vis[j])

            {

                if(dist[j]>=(dist[mark]+ma[mark][j])&&mark!=x&&mark!=j) {vis3[j]=1;}

                dist[j]=min(dist[j],dist[mark]+ma[mark][j]);

            }

        }

    }

    for(i=1; i<=n; i++)

    {  //printf("*%lld*",vis3[i]);

        if(dist[i]<=ma[x][i])

        {

            if(vis3[i]==1){vis2[x][i]=1;vis2[i][x]=1;}

            if(dist[i]<ma[x][i])

            {

                flag=1;

            }

        }

    }

   //printf("\n");

}

int main()

{

    scanf("%lld",&n);

    for(i=1; i<=n; i++)

    {

        for(j=1; j<=n; j++)

        {

            scanf("%lld",&ma[i][j]);

        }



    }

    ans=0;

    flag=0;



    for(l=1; l<=n; l++)

    {

        dijkstra(l);

        if(flag==1) break;

    }

    if(flag==0)

    {

        for(i=1; i<=n; i++)



        {

            for(j=i+1; j<=n; j++)

            {

                if(vis2[i][j]!=1) ans+=ma[i][j];

            }

        }

        printf("%lld\n",ans);

    }

    else printf("-1\n");

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 5.897716306326371x):
#pragma GCC optimize("O1")

#pragma GCC optimize("O2")

#pragma GCC optimize("O3")

#include<cstdio>

#define LL long long

#define N 310

int n;

LL g[N][N];

signed main()

{

	scanf("%d",&n);LL ans(0);

	for(register int i(1);i<=n;i++)

		for(register int j(1);j<=n;j++)

			scanf("%lld",&g[i][j]);

	for(register int i(1);i<=n;i++)

		for(register int j(1);j<=i;j++)

		{

			bool f(1);

			for(register int k(1);k<=n;k++)

				if(g[i][j]>g[i][k]+g[k][j])

					return puts("-1"),0;

				else if(i-k&&j-k&&g[i][j]==g[i][k]+g[k][j])

					f=0;

			ans+=g[i][j]*f;

		}

	return printf("%lld\n",ans),0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

using namespace std;

long long a[310][310];

bool b[310][310];

int main() {



//	freopen("4.in","r",stdin);



	long long n,ans=0;

	int i,j,k;



	scanf("%lld",&n);



	for(i=1; i<=n; i++) {

		for(j=1; j<=n; j++) {

			scanf("%lld",&a[i][j]);

		}

	}



	for(i=1; i<=n; i++) {

		for(j=1; j<=n; j++) {

			for(k=1; k<=n; k++) {

				if(i!=j&&j!=k&&k!=i) {

					if(a[i][j]==a[i][k]+a[k][j]) b[i][j]=1;

					if(a[i][j]>a[i][k]+a[k][j]) {

						printf("-1");

						return 0;

					}

				}

			}

		}

	}



	for(i=1; i<=n; i++) {

		for(j=1; j<=n; j++) {

			if(!b[i][j]) ans+=a[i][j];

		}

	}

	

	printf("%lld",ans/2);



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.209570908021843x):
#include<stdio.h>

int a[305][305];

bool v[305][305];

long long ans;

main(){

	int n;scanf("%d",&n);

	for(register int i=1;i<=n;i++)

		for(register int j=1;j<=n;j++)

			scanf("%d",&a[i][j]);

	for(register int k=1;k<=n;k++){

		for(register int i=1;i<=n;i++){

			for(register int j=1;j<=n;j++){

				if(k!=i&&k!=j&&i!=j){

					if(a[i][j]==a[i][k]+a[k][j])

						v[i][j]=1;

					else if(a[i][j]>a[i][k]+a[k][j]){

						puts("-1");

						return 0;

					}

				}

			}

		}

	}

	for(register int i=1;i<=n;i++)

		for(register int j=1;j<=n;j++)

			if(!v[i][j])

				ans+=a[i][j];

	printf("%lld\n",ans/2);

	return 0; 

}
// Slower C++ solution:


#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<string>

#include<cstring>

#include<cmath>

#include<ctime>

#include<algorithm>

#include<utility>

#include<stack>

#include<queue>

#include<vector>

#include<set>

#include<map>

#include<bitset>

#define EPS 1e-9

#define PI acos(-1.0)

#define INF 0x3f3f3f3f

#define LL long long

const int MOD = 1E9+7;

const int N = 1000+5;

const int dx[] = {-1,1,0,0,-1,-1,1,1};

const int dy[] = {0,0,-1,1,-1,1,-1,1};

using namespace std;

 

LL G[N][N];

int main() {

    int n;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        for(int j=1;j<=n;j++)

            scanf("%lld",&G[i][j]);

 

    bool flag=false;

    LL res=0;

    for(int i=1;i<=n&&!flag;i++){

        for(int j=i+1;j<=n&&!flag;j++){

            bool flag2=false;

            for(int k=1;k<=n&&!flag;k++){

                if(G[i][k]+G[k][j]<G[i][j])

                    flag=true;

                else{

                    if(i!=k&&j!=k&&G[i][j]==G[i][k]+G[k][j])

                        flag2=true;

                }

            }

            if(!flag2)

                res+=G[i][j];

        }

    }

 

    if(flag)

        printf("-1\n");

    else

        printf("%lld\n",res);

 

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.210749832285921x):
#include<stdio.h>

int a[305][305];

bool v[305][305];

long long ans;

main(){

	int n;scanf("%d",&n);

	for(register int i=1;i<=n;i++)

		for(register int j=1;j<=n;j++)

			scanf("%d",&a[i][j]);

	for(register int k=1;k<=n;k++){

		for(register int i=1;i<=n;i++){

			for(register int j=1;j<=n;j++){

				if(k!=i&&k!=j&&i!=j){

					if(a[i][j]==a[i][k]+a[k][j])

						v[i][j]=1;

					else if(a[i][j]>a[i][k]+a[k][j]){

						puts("-1");

						return 0;

					}

				}

			}

		}

	}

	for(register int i=1;i<=n;i++)

		for(register int j=1;j<=n;j++)

			if(!v[i][j])

				ans+=a[i][j];

	printf("%lld\n",ans/2);

	return 0; 

}
// Slower C++ solution:
#include<iostream>

#include<cstring>

using namespace std;

int main(){



    long long int n,ans=0,i,j,k;

    cin>>n;

    long long int a[n+1][n+1];

    bool p[n+1][n+1];

    memset(p,0,sizeof(p));

    for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

            cin>>a[i][j];

    //读入数据以及初始化操作



    for(k=1;k<=n;k++)      

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++){

                if(k!=j&&k!=i&&i!=j){

                    if(a[i][j]==a[i][k]+a[k][j])

                        p[i][j]=1;  //标记

                    if(a[i][j]>a[i][k]+a[k][j]){

                        cout<<"-1"<<endl;  //不是最短路，无解

                        return 0;

                    }

                }

            }

    //核心操作语句



    for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

            if(p[i][j]==0)

                ans+=a[i][j]; //统计长度总和

    cout<<ans/2<<endl;

    //统计总和及输出



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.285591215095603x):
#include<stdio.h>

int a[305][305];

bool v[305][305];

long long ans;

main(){

	int n;scanf("%d",&n);

	for(register int i=1;i<=n;i++)

		for(register int j=1;j<=n;j++)

			scanf("%d",&a[i][j]);

	for(register int k=1;k<=n;k++){

		for(register int i=1;i<=n;i++){

			for(register int j=1;j<=n;j++){

				if(k!=i&&k!=j&&i!=j){

					if(a[i][j]==a[i][k]+a[k][j])

						v[i][j]=1;

					else if(a[i][j]>a[i][k]+a[k][j]){

						puts("-1");

						return 0;

					}

				}

			}

		}

	}

	for(register int i=1;i<=n;i++)

		for(register int j=1;j<=n;j++)

			if(!v[i][j])

				ans+=a[i][j];

	printf("%lld\n",ans/2);

	return 0; 

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

int main()

{



    long long int n,ans=0,i,j,k;

    cin>>n;

    long long int a[n+1][n+1];

    bool p[n+1][n+1];

    memset(p,0,sizeof(p));

    for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

            cin>>a[i][j];

    for(k=1;k<=n;k++)      

        for(i=1;i<=n;i++)

            for(j=1;j<=n;j++){

                if(k!=j&&k!=i&&i!=j){

                    if(a[i][j]==a[i][k]+a[k][j])

                        p[i][j]=1; 

                    if(a[i][j]>a[i][k]+a[k][j]){

                        cout<<"-1"<<endl;  

                        return 0;

                    }

                }

            }





    for(i=1;i<=n;i++)

        for(j=1;j<=n;j++)

            if(p[i][j]==0)

                ans+=a[i][j]; 

    cout<<ans/2<<endl;



    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.285591215095603x):
#include<stdio.h>

int a[305][305];

bool v[305][305];

long long ans;

main(){

	int n;scanf("%d",&n);

	for(register int i=1;i<=n;i++)

		for(register int j=1;j<=n;j++)

			scanf("%d",&a[i][j]);

	for(register int k=1;k<=n;k++){

		for(register int i=1;i<=n;i++){

			for(register int j=1;j<=n;j++){

				if(k!=i&&k!=j&&i!=j){

					if(a[i][j]==a[i][k]+a[k][j])

						v[i][j]=1;

					else if(a[i][j]>a[i][k]+a[k][j]){

						puts("-1");

						return 0;

					}

				}

			}

		}

	}

	for(register int i=1;i<=n;i++)

		for(register int j=1;j<=n;j++)

			if(!v[i][j])

				ans+=a[i][j];

	printf("%lld\n",ans/2);

	return 0; 

}
// Slower C++ solution:
#include<iostream>

using namespace std;

typedef long long ll;

const int N = 301;

int a[N][N];

ll sum;

int main() {

	int n;



	cin >> n;

	for (int i = 1; i <= n; i++)

		for (int j = 1; j <= n; j++)

			cin >> a[i][j];



	for(int i=1;i<=n;i++)

		for (int j = i; j <= n; j++) {

			bool temp = true;

			for (int k = 1; k <= n; k++) {

				if (k == i || k == j)

					continue;

				if (a[i][k] + a[k][j] < a[i][j]) {

					cout << -1 << endl;

					return 0;

				}

				if (a[i][k] + a[k][j] == a[i][j])

					temp = false;

			}

			if (temp)

				sum += a[i][j];

		}



	cout << sum << endl;



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2920572344353705x):
#include<cstdio>

#define LL long long

#define N 310

int n;

LL g[N][N];

signed main()

{

	scanf("%d",&n);LL ans(0);

	for(register int i(1);i<=n;i++)

		for(register int j(1);j<=n;j++)

			scanf("%lld",&g[i][j]);

	for(register int i(1);i<=n;i++)

		for(register int j(1);j<=i;j++)

		{

			bool f(1);

			for(register int k(1);k<=n;k++)

				if(g[i][j]>g[i][k]+g[k][j])

					return puts("-1"),0;

				else if(i-k&&j-k&&g[i][j]==g[i][k]+g[k][j])

					f=0;

			ans+=g[i][j]*f;

		}

	return printf("%lld\n",ans),0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <cstdio> 

using namespace std;



typedef long long LL;



const int MAXN = 320;

const int INF = 1e9 + 100;



int n, dis[MAXN][MAXN];



namespace Part1 {

	struct Edge {

		int u, v;

	}; 

	bool tag[MAXN * MAXN];

	vector<Edge> e;

	int G[MAXN][MAXN];

	LL ans(2e18);

	void Judge() {

		LL cost = 0LL;

		for(int i = 1; i <= n; i ++)

			for(int j = 1; j <= n; j ++)

				G[i][j] = i == j ? 0 : INF;

		for(int i = 0; i < e.size(); i ++) 

			if(tag[i]) {

				cost += dis[ e[i].u ][ e[i].v ];

				if(cost > ans) return ;

				G[ e[i].u ][ e[i].v ] = G[ e[i].v ][ e[i].u ] = dis[ e[i].u ][ e[i].v ];

			}

		for(int k = 1; k <= n; k ++)

			for(int i = 1; i <= n; i ++)

				for(int j = 1; j <= n; j ++)

					if(G[i][k] < INF && G[k][j] < INF)

						G[i][j] = min(G[i][j], G[i][k] + G[k][j]);

		for(int i = 1; i <= n; i ++)

			for(int j = i + 1; j <= n; j ++)

				if(dis[i][j] != G[i][j]) return ;

		if(ans > cost) ans = cost;

	}

	

	void dfs(int k, int m) {

		if(k == m) {

			Judge() ;

			return ;

		}

		tag[k] = true, dfs(k + 1, m);

		tag[k] = false, dfs(k + 1, m);

	}

	

	int main() {

		for(int i = 1; i <= n; i ++)

			for(int j = i + 1; j <= n; j ++)

				e.push_back((Edge) {i, j});

		for(int i = 0; i < e.size(); i ++) tag[i] = false;

		dfs(0, (int) e.size());

		printf("%lld\n", ans == 2e18 ? -1 : ans);

		return 0;

	}

}



namespace Part2 {

	int main() {

		LL ans = 0;

		for(int i = 1; i <= n; i ++) {

			for(int j = 1; j <= n; j ++) {

				bool flag = false;

				for(int k = 1; k <= n; k ++) {

					if(k == i || k == j) continue ;

					if(dis[i][k] + dis[k][j] == dis[i][j]) {

						flag = true;

						break ;

					}

				}

				if(!flag) ans += dis[i][j];

			}

		}

		printf("%lld\n", ans / 2LL);

		return 0;

	}

}



bool error__() {

	for(int k = 1; k <= n; k ++)

		for(int i = 1; i <= n; i ++)

			for(int j = 1; j <= n; j ++)

				if(dis[i][j] > dis[i][k] + dis[k][j]) return true;

	return false;

}



int main() {

	scanf("%d", &n);

	for(int i = 1; i <= n; i ++) {

		for(int j = 1; j <= n; j ++) {

			scanf("%d", &dis[i][j]);

		}

	}

	if(error__()) return puts("-1"), 0;



	if(n <= 6) Part1 :: main();

	else Part2 :: main(); 

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.268158714664383x):
#include<cstdio>

#define LL long long

#define N 310

int n;

LL g[N][N];

signed main()

{

	scanf("%d",&n);LL ans(0);

	for(register int i(1);i<=n;i++)

		for(register int j(1);j<=n;j++)

			scanf("%lld",&g[i][j]);

	for(register int i(1);i<=n;i++)

		for(register int j(1);j<=i;j++)

		{

			bool f(1);

			for(register int k(1);k<=n;k++)

				if(g[i][j]>g[i][k]+g[k][j])

					return puts("-1"),0;

				else if(i-k&&j-k&&g[i][j]==g[i][k]+g[k][j])

					f=0;

			ans+=g[i][j]*f;

		}

	return printf("%lld\n",ans),0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

vector<vector<long long > > A(310, vector<long long > (310)), dist(310, vector<long long > (310));

int main() {

    int n;

    cin >> n;

    for(int i=0;i<n;i++)

	{

        for(int j=0;j<n;j++)

		{

            cin >> A[i][j];

            dist[i][j]=A[i][j];

        }

    }

    for(int k=0;k<n;k++) 

	{

        for(int i=0;i<n;i++)

		{

            for(int j=0;j<n;j++)

			{

                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);

            }

        }

    }

    long long ans=0;

    for(int i=0;i<n-1;i++)

	{

        for(int v=i+1;v<n;v++)

		{

            if(dist[i][v]<A[i][v])

			{

                cout<<-1<<endl;

                return 0;

            }

            int flag = 0;

            for(int j=0;j<n;j++)

			{

                if(j!=i&&j!=v&&dist[i][v]==dist[i][j]+dist[j][v])

				{

                    flag=1;

                }

            }

            if(!flag)

			{

                ans+=dist[i][v];

            }

        }

    }

    cout<<ans<<endl;

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.13215936113712x):
#include <bits/stdc++.h>

using namespace std;



#define REP(i,n) for(int (i)=0; i<(int)(n); i++)



long long a[310][310];

bool used[310][310];



int main(void){

    long long N,ans=0;

    cin >> N;

    REP(i,N) REP(j,N)

        cin >> a[i][j];

    REP(k,N) REP(i,N) REP(j,N)

        if(k!=j && k!=i && i!=j) {

            if(a[i][j] == a[i][k]+a[k][j])

                used[i][j] = true;

            if(a[i][j] > a[i][k]+a[k][j]) {

                cout << "-1" << endl;

                return 0;

            }

        }

    REP(i,N) REP(j,N)

        if(used[i][j] == false) ans += a[i][j];

    cout << ans/2 << endl;

    return 0;

}