import java.io.IOException;

class Graph{

    String [] knoten = {
                    "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" };
    int knotenZahl =  knoten.length;
    int[][] kanten =
       {{ 0, 18,  0, 12, 20,  0,  0,  0,  0,  0,  0,  0,  0,  0, 15},
	    {18,  0, 15,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0},
	    { 0, 15,  0, 15,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0},
	    {12,  0, 15,  0,  0, 20,  0,  0,  0,  0,  0,  0,  0,  0,  0},
	    {20,  0,  0,  0,  0, 20, 18,  0,  0,  0,  0,  0,  0, 25,  0},
	    { 0,  0,  0, 20, 20,  0,  0, 14,  0,  0,  0,  0,  0,  0,  0},
	    { 0,  0,  0,  0, 18,  0,  0, 15,  0, 10,  0,  0,  0,  0,  0},
	    { 0,  0,  0,  0,  0, 14, 15,  0, 20,  0,  0,  0,  0,  0,  0},
	    { 0,  0,  0,  0,  0,  0,  0, 20,  0, 15,  0, 60,  0,  0,  0},
	    { 0,  0,  0,  0,  0,  0, 10,  0, 15,  0, 35,  0,  0,  0,  0},
	    { 0,  0,  0,  0,  0,  0,  0,  0,  0, 35,  0,  0, 10,  0,  0},
	    { 0,  0,  0,  0,  0,  0,  0,  0, 60,  0,  0,  0, 70,  0,  0},
	    { 0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 10, 70,  0, 50,  0},
	    { 0,  0,  0,  0, 25,  0,  0,  0,  0,  0,  0,  0, 50,  0, 15},
	    {15,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0, 15,  0}};

	private final int ariMax = 2;
	private int schranke;
	private int wegeMax = 5*knotenZahl;
	private int[] minWeg = new int[wegeMax];
	private int aktWegLaenge;
	
	private static boolean [] besucht;
	

	int kante(int k1, int k2){ return kanten[k1] [k2];}

    void dfVisit(int k){
        besucht = new boolean [knotenZahl];
        rekDFVisit(k);
        }

    
     void rekDFVisit(int k){
         int max = knotenZahl;
	 if ( !besucht[k] ){
	     besucht[k] = true;
	     System.out.println(knoten[k]);
	     for (int n = 0; n < max; n++)
	     if (kanten[k][n] > 0) rekDFVisit(n);
	     }
	} 

    void bfVisit(int k){
      int max = knotenZahl;
			boolean [] besucht = new boolean [max];
			Queue q = new Queue(max+5);
			try {
			   q.enQueue(k);
			   while(!q.istLeer()){
				 int l = q.deQueue();
				 if (!besucht[l] ){
				   besucht[l]= true;
				   System.out.println(knoten[l]);
				   for (int n = 0; n < max; n++)
					 if (kanten[l][n] > 0) q.enQueue(n);
				   }
				}
	    }
			catch(QueueFehler s){ 
			   System.out.println("Fehler bei der Breitensuche: "+s);
			   }
			} 

    void minSuche(int u, int v){
       int max = knotenZahl;
       boolean [] s = new boolean[max];
       for (int i = 0; i < max; i++) s[i] = false;
       s[u] = true;
       int [] minEntf = new int [max];
       for (int i = 0; i < max; i++) minEntf[i] = 0;
       while (!s[v]){
         int minMin = 1000000;
         int minInd = 0;
         for (int k1 = 0; k1 < max; k1++)
           for (int k2 = 0; k2 < max; k2++)
            if (s[k1] && !s[k2] && (kanten[k1][k2] > 0)){
                int minNeu = kanten[k1][k2] + minEntf[k1];
                if (minNeu < minMin){
                    minMin = minNeu;
                    minInd = k2;
                    }
                }
         s[minInd] = true;
         minEntf[minInd] = minMin;
         System.out.println("nach "+ knoten[minInd] + " ist " + minMin + " km.");
         }
      }

    private int wegLaenge(int[] weg, int maxIndex){
        int erg = 0;
        for (int w = 0; w < maxIndex; w++) erg += kanten[weg[w]][weg[w+1]];
        return erg;
        }

    private boolean testeWeg(int[] weg, int[] marken, int maxIndex, int ziel){
        if (weg[maxIndex] != ziel) return false;
        int max = knotenZahl;
        if (maxIndex < (max-1)) return false;
        for (int k = 0; k < max; k++) if (marken[k] == 0) return false;
        return true;
        }

     private void Besuche(int k, int[] weg, int maxIndex, int ziel, int[] marken){
        int max = knotenZahl;
        maxIndex++;
        if (maxIndex >= (wegeMax-2)){
          System.out.println("Der Weg wurde zu lang .....");
          return;
          }
        weg[maxIndex] = k;
        int bisherigeLaenge = 0;
        if (maxIndex == 0) aktWegLaenge = 0;
        else {
            bisherigeLaenge = aktWegLaenge;
            aktWegLaenge += kanten[weg[maxIndex-1]][weg[maxIndex]];
            }
        marken[k]++;
        // int NeueLaenge = wegLaenge(weg, maxIndex);
        if (aktWegLaenge < schranke){
            if (testeWeg(weg, marken, maxIndex, ziel )){
                System.arraycopy(weg, 0, minWeg, 0, maxIndex+2);
                schranke = aktWegLaenge;
                }
            else{
                for (int n = 0; n < max; n++)
                    if (kanten[k][n] > 0)
                        if (marken[n] < ariMax)
                            Besuche(n, weg, maxIndex, ziel, marken);
                }
            }
        // Besuch wieder rückgängig machen:
        aktWegLaenge = bisherigeLaenge;
        weg[maxIndex] = -1;
        marken[k]--;
        }

     void TSP(int u, int v){
        int max = knotenZahl;
         
        //int s = 0;
        // Automatisches Abschätzung für Schranke
        //for (int x=0; x < max; x++)
           //for (int y=0; y < max; y++) s += kanten[x][y];

        // Bzw. Experimentelles Setzen der Schranke
        int s =370;
        
        schranke = s;
        
        int[] weg = new int[wegeMax];
        for (int i = 0; i < wegeMax; i++) weg[i] = -1;
        System.arraycopy(weg, 0, minWeg, 0, wegeMax);
        int[] marken = { 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0 };
        int maxIndex = -1;
        long Zeit1 = System.currentTimeMillis();
        Besuche(u, weg, maxIndex, v, marken);
        long Zeit2 = System.currentTimeMillis();
        System.out.println("LaufZeit: "+(Zeit2-Zeit1));
        if ( s == schranke){
          System.out.println("Kein Weg gefunden !!!");
          return;
          }
        System.out.println("Länge des kürzesten Weges: "+ schranke);
        System.out.println("Der kürzeste Weg ist: ");
        int knotenNr = minWeg[0];
        int WegIndex = 1;
        while (knotenNr >= 0){
            for (int i=0; i < (2*WegIndex+10); i++)System.out.print(' ');
            System.out.println(knoten[knotenNr]);
            knotenNr = minWeg[WegIndex];
            WegIndex++;
            }
        }
    }


public class GraphT {

    public static void main(String args[]) {
        System.out.println("Graph Tester");
        Graph meinGraph = new Graph();
        /* for (int i = 0; i < meinGraph.knoten.length; i++)
           System.out.println(meinGraph.knoten[i]); */
        /*meinGraph.DFVisit(0);
        meinGraph.BFVisit(0);*/
        /*Warshall w = new Warshall();
        System.out.println(w.knotenZahl);*/

        /*System.out.println("Min-Suche Ausgangsknoten: " + meinGraph.knoten[1]);
        System.out.println("              Zielknoten: " + meinGraph.knoten[10]);
        meinGraph.minSuche(1,10);*/

        /*System.out.println("TSP Ausgangsknoten: " + meinGraph.knoten[0]);
        System.out.println("        Zielknoten: " + meinGraph.knoten[1]);
        meinGraph.TSP(0,1);*/
        
        System.out.println("TSP Ausgangsknoten: " + meinGraph.knoten[0]);
        System.out.println("        Zielknoten: " + meinGraph.knoten[4]);
        meinGraph.TSP(0,4);

        System.out.println("");
        
    }
}


class Warshall{
    boolean [][] A = {
                            {false, false, true, true, false},
                            {false, true, false, true, false},
                            {true, false, true, false, false},
                            {false, true, true, true, false},
                            {true, true, false, true, false},
                            };
    int dim =  A.length;

    void WarshallAlg(){
        int max = dim;
        for (int y = 0; y < max; y++)
            for (int x = 0; x < max; x++)
                if (A[x][y]) for (int z = 0; z < max; z++)
                    if (A[y][z]) A[x][z] = true;
        }

}


class QueueFehler extends Exception{
    public QueueFehler(){super();}
    public QueueFehler(String s){super(s);}
}

class Queue{
    private int[] Inhalt = null;
    private boolean voll = false;
    private int Anfang = 0;
    private int Ende = 0;
    private int maxIndex;

    Queue(int sz){
      Inhalt = new int[sz+1];
      maxIndex = sz-1;
      }

    private int next(int n){
        if ( n == maxIndex) return 0;
        return ++n;
        }

    boolean istLeer (){ return (Anfang == Ende) && ! voll;}
    boolean istVoll (){ return voll;}

    void enQueue (int k) throws QueueFehler{
     if (Inhalt == null) throw new QueueFehler("QueueFehler: Keine Queue gefunden !");
     if (istVoll()) throw new QueueFehler("QueueFehler: Queue Überlauf !");
     Inhalt[Ende] = k;
     Ende = next(Ende);
     voll = (Anfang == Ende);
     }

    int deQueue () throws QueueFehler {
     if (Inhalt == null) throw new QueueFehler("QueueFehler: Keine Queue gefunden !");
     if (istLeer()) throw new QueueFehler("QueueFehler: Zugriff auf leere Queue !");
     int k = Inhalt[Anfang];
     Anfang = next(Anfang);
     voll = false;
     return k;
     }
}