#include "rail.h"
#include <bits/stdc++.h>
using namespace std;
/*
int diste[109][109];
int getDistance(int a, int b){
return diste[a][b];
}
*/
int memo[5009][5009];
int dist(int a, int b){
if(memo[a][b] != -1) return memo[a][b];
return memo[a][b] = getDistance(a,b);
}
void findLocation(int N, int first, int location[], int stype[]){
for(int i = 0; i < 5009; i++){
for(int j = 0; j < 5009; j++){
memo[i][j] = -1;
}
}
stype[0] = 1;
location[0] = first;
int R;
vector<int> visited(N,false);
visited[0] = true;
int p = -1;
while(1){
int maxi = INT_MAX;
for(int i = 1; i < N; i++){
if(dist(0,i) < maxi && !visited[i] && dist(0,i) != dist(0,p)+dist(p,i)){
maxi = dist(0,i);
R = i;
}
}
if(maxi == INT_MAX)
break;
if(p == -1) p = R;
stype[R] = 2;
location[R] = first+dist(0,R);
visited[R] = true;
for(int i = 1; i < N; i++){
if(!visited[i] && dist(0,i) == dist(0,R)+dist(R,i) && dist(R,i) < dist(0, R)){
location[i] = first+dist(0,R)-dist(R,i);
stype[i] = 1;
visited[i] = true;
}
}
}
int L = 0;
while(1){
int maxi = INT_MAX;
for(int i = 1; i < N; i++){
if(dist(0,i) < maxi && !visited[i]){
maxi = dist(0,i);
L = i;
}
}
if(maxi == INT_MAX) break;
location[L] = first-(dist(0,L)-2*dist(0,p));
stype[L] = 1;
visited[L] = true;
for(int i = 1; i < N; i++){
if(!visited[i] && dist(0,i) == dist(0,L)+dist(L,i) && dist(L,i) < dist(0,L)-2*dist(0,p)){
stype[i] = 2;
location[i] = location[L]+dist(L,i);
visited[i] = true;
}
}
}
}
/*
int main(){
int n;
cin >> n;
int first;
cin >> first;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> diste[i][j];
}
}
int location[n];
int stype[n];
for(int i = 0; i < n; i++){
location[i] = INT_MAX;
stype[i] = INT_MAX;
}
findLocation(n,first, location,stype);
cout << endl;
for(int a : location) cout << a << ' ';
cout << endl;
for(int a : stype) cout << a << ' ';
cout << endl;
}
/*
5 4
0 12 4 15 7
12 0 8 3 11
4 8 0 11 3
15 3 11 0 14
7 11 3 14 0
*/
