#include <bits/stdc++.h>
using namespace std;
#define mx ((int)1e9)
int n,k;
int g[301][301];
void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
g[i][j]=g[j][i]=min(g[i][j],g[i][k]+g[k][j]);
}
}
}
}
long long upd(int a,int b,int c){
if(c>g[a][b])return (long long)0;
int old=g[a][b],diff=c-g[a][b];
long long sum=diff;
g[a][b]=g[b][a]=c;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
int tmp=min(g[i][a]+c+g[b][j],g[i][b]+c+g[a][j]);
if(tmp<g[i][j]){
sum+=tmp-g[i][j];
g[i][j]=g[j][i]=tmp;
}
}
}
return sum;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(NULL);
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>g[i][j];
cin>>k;
floyd();
long long sum=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
sum+=g[i][j];
for(int i=1;i<=k;i++){
int a,b,c;
cin>>a>>b>>c;
sum+=upd(a,b,c);
cout<<' '<<sum;
}
return 0;
}
Comments
Post a Comment