import java.io.*;

import java.util.*;

public class dining {

static final int V=9;

static int minDistance(int dist[], boolean[] sptSet) {

int min = Integer.MAX_VALUE, min_index=-1; // Computers are too stupid to understand infinite

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)

{

min = dist[v];

min_index = v;

}

return min_index;

}

static void dijkstra(int graph[][], int src) {

int dist[] = new int[V];

boolean sptSet[] = new boolean[V];

for (int i = 0; i < V; i++) {

dist[i] = Integer.MAX_VALUE;

sptSet[i] = false;

}

dist[src] = 0;

for (int count = 0; count < V-1; count++) {

int u = minDistance(dist, sptSet);

sptSet[u] = true;

for (int v = 0; v < V; v++)

if (!sptSet[v] && graph[u][v]!=0 &&

dist[u] != Integer.MAX_VALUE &&

dist[u]+graph[u][v] < dist[v])

dist[v] = dist[u] + graph[u][v];

}

}

public static void main(String[] args) {

BufferedReader f = new BufferedReader();

}

}