#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int maxn=505;
int d[maxn][maxn];
int vis[maxn][maxn];
int n;
inline int calc(int x,int y){
	if(x>y)swap(x,y);
	return x*501+y;
}
inline void solv(int x){
	int a=x/501,b=x%501;
	vis[a][b]=vis[b][a]=1;
}
vector<int>merge(vector<int>a,vector<int>b,int x){
	int now=0;
	vector<int>t;
	for(auto u:a){
		while(now<b.size()&&b[now]<u)now++;
		if((now<b.size()&&b[now]==u)||u==x)t.push_back(u);
	}
	return t;
}
void dij(int x){
	priority_queue<pii,vector<pii>,greater<pii>>q;
	q.push({0,x});
	vector<int>dis(n+5,1e9);
	dis[x]=0;
	vector<vector<int>>from(n+5);
	while(!q.empty()){
		int x=q.top().second,t=q.top().first;
		q.pop();
		sort(from[x].begin(),from[x].end());
		if(t!=dis[x])continue;
		for(int i=1;i<=n;i++){
			if(i==x)continue;
			if(t+d[x][i]<dis[i]){
				from[i]=from[x];
				int tmp=calc(x,i);
				for(int j=0;j<from[i].size();j++){
					if(from[i][j]>tmp){
						from[i].insert(from[i].begin()+j,tmp);
						break;
					}
					if(j+1==from[i].size()){
						from[i].push_back(tmp);
						break;
					}
				}
				if(from[i].empty())from[i]={tmp};
				dis[i]=t+d[x][i];
				q.push({t+d[x][i],i});
			}
			else if(t+d[x][i]==dis[i]){
				from[i]=merge(from[i],from[x],calc(x,i));
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(auto u:from[i]){
			solv(u);
		}
	}
}
void solve(){
//	cin>>n;
	n=500;
	srand(time(0));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
//			cin>>d[i][j];
			if(i<j)d[i][j]=rand();
			else d[i][j]=d[j][i];
		}
	}
	for(int i=1;i<=n;i++)dij(i);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
//			cout<<vis[i][j];
		}
//		cout<<"\n";
	}
}
int main(){
//    ios::sync_with_stdio(0);cin.tie(0);
    int t=1;
    // cin>>t;
    while(t--)solve();
    return 0;
}
/*
4
0 3 2 100
3 0 8 100
2 8 0 10
100 100 10 0
*/