class Knoten{
    String  name;
    boolean markiert;
    Knoten(String s){ name = s; }
    public String toString(){ return name;}
}

class Graph{

    static final private int U  = Integer.MAX_VALUE;
    
    Knoten [] knoten;
    int knotenZahl;
    
    int[][] distanzen =
       {{ U, 18,  U, 12, 20,  U,  U,  U,  U,  U,  U,  U,  U,  U, 15},
	    {18,  U, 15,  U,  U,  U,  U,  U,  U,  U,  U,  U,  U,  U,  U},
	    { U, 15,  U, 15,  U,  U,  U,  U,  U,  U,  U,  U,  U,  U,  U},
	    {12,  U, 15,  U,  U, 20,  U,  U,  U,  U,  U,  U,  U,  U,  U},
	    {20,  U,  U,  U,  U, 20, 18,  U,  U,  U,  U,  U,  U, 25,  U},
	    { U,  U,  U, 20, 20,  U,  U, 14,  U,  U,  U,  U,  U,  U,  U},
	    { U,  U,  U,  U, 18,  U,  U, 15,  U, 10,  U,  U,  U,  U,  U},
	    { U,  U,  U,  U,  U, 14, 15,  U, 20,  U,  U,  U,  U,  U,  U},
	    { U,  U,  U,  U,  U,  U,  U, 20,  U, 15,  U, 60,  U,  U,  U},
	    { U,  U,  U,  U,  U,  U, 10,  U, 15,  U, 35,  U,  U,  U,  U},
	    { U,  U,  U,  U,  U,  U,  U,  U,  U, 35,  U,  U, 10,  U,  U},
	    { U,  U,  U,  U,  U,  U,  U,  U, 60,  U,  U,  U, 70,  U,  U},
	    { U,  U,  U,  U,  U,  U,  U,  U,  U,  U, 10, 70,  U, 50,  U},
	    { U,  U,  U,  U, 25,  U,  U,  U,  U,  U,  U,  U, 50,  U, 15},
	    {15,  U,  U,  U,  U,  U,  U,  U,  U,  U,  U,  U,  U, 15,  U}};
       		
    Graph(){
    	String [] sk = { "San Francisco", "San Rafael", "Richmond",
                       "Oakland", "San Mateo", "Hayward",
                       "Palo Alto", "Fremont", "San Jose",
                       "Santa Clara", "Scotts Valley", "Watsonville",
                       "Santa Cruz", "Half Moon Bay", "Pacifica" };
      knotenZahl = sk.length;
      knoten = new Knoten [knotenZahl];
      for (int i=0; i < knotenZahl; i++) knoten[i] = new Knoten(sk[i]);
      }
    
    void floyd(){
       int l = knotenZahl;
       for (int y=0; y < l; y++)
         for (int x=0; x < l; x++)
           if (distanzen[x][y] < U)
             for (int z=0; z < l; z++)
               if (distanzen[y][z] < U)
                 distanzen[x][z] = Math.min(distanzen[x][z], distanzen[x][y]+distanzen[y][z]);
       }	    		

     void showDistanzen(){
     	int l = knotenZahl;
       for (int x=0; x < l; x++){
         for (int y=0; y < l; y++) System.out.printf("%4d",distanzen[x][y]);
         System.out.println();       
         }
      }
    }


public class GraphT {

    public static void main(String ... args) {
     Graph g = new Graph();
     g.floyd();
     g.showDistanzen();

    }
}