namespace Johnson
{
vector<pii> G[MAX];
int ans[MAX][MAX];
int dis[MAX],vis[MAX],con[MAX]; queue<int> q;
int Dis[MAX],Vis[MAX]; priority_queue<pii> Q;
inline bool SPFA(int s)
{
while(!q.empty()) q.pop();
memset(vis,0,sizeof vis),memset(dis,0x3f,sizeof dis),memset(con,0,sizeof con);
vis[s]=1,dis[s]=0,q.emplace(s);
while(!q.empty())
{
int now=q.front(); q.pop();
vis[now]=0;
for(auto [to,val]:G[now]) if(dis[to]>dis[now]+val)
{
dis[to]=dis[now]+val,con[to]=con[now]+1;
if(con[now]>=n) return 1;
if(!vis[to]) vis[to]=1,q.emplace(to);
}
}
return 0;
}
inline void dijkstra(int s)
{
memset(Vis,0,sizeof Vis),memset(Dis,0x3f,sizeof Dis);
Dis[s]=0,Q.emplace(mp(0,s));
while(!Q.empty())
{
int now=Q.top().second; Q.pop();
if(Vis[now]) continue;
Vis[now]=1;
for(auto [to,val]:G[now]) if(Dis[to]>Dis[now]+val) Dis[to]=Dis[now]+val,Q.emplace(mp(-Dis[to],to));
}
}
inline bool solve()
{
for(int i=1;i<=n;++i) G[0].eb(mp(i,0));
if(SPFA(0)) return 1;
for(int i=1;i<=n;++i) for(int j=0;j<((int)G[i].size());++j) G[i][j].se+=dis[i]-dis[G[i][j].fi];
for(int i=1;i<=n;++i)
{
dijkstra(i);
for(int j=1;j<=n;++j) if(Dis[j]==INF) ans[i][j]=-1; else ans[i][j]=Dis[j]+dis[j]-dis[i];
}
return 0;
}
}