import java.util.*;
import java.io.*; 
import java.nio.*;


// Ein Objekt der Klasse Edge repräsentiert eine Kante,
// welche charakterisiert ist durch Quellknoten, Zielknoten und Gewicht

class Edge{
	Edge()
	{
		src=trg=weight=-1;
	}
	Edge(int s, int t, int w)
	{
		src=s; trg=t; weight=w;
	}
	public int src;
	public int trg;
	public int weight;
}

public class Dijkstra {

    static int nofNodes;			// # Knoten im Graph
    static int nofEdges;			// # Kanten im Graph

    static double [] xCoords;		// X-Koordinaten der Knoten (eigentl. momentan ueberfluessig)
    static double [] yCoords;		// Y-Koordinaten ..... dito
    static Edge [] edgeList;		// Liste der Kanten
    static int [] edgeOffsets;		// edgeOffsets --- von Ihnen noch zu füllen


    public static void readGraph(String filename)	// folgende Methode liest aus einer Datei einen Graph ein,
	   						// und füllt die Variablen nofNodes, nofEdges sowie die
							// Arrays xCoords, yCoords, edgeList.
							// edgeOffsets muss von Ihnen noch sinnvoll gefüllt werden!
    {
	    try {
	     Scanner sc = new Scanner(new File(filename));
	     sc.useLocale(new Locale("eng"));
	     nofNodes=sc.nextInt();
	     nofEdges=sc.nextInt();

	     xCoords=new double[nofNodes];
	     yCoords=new double[nofNodes];
	     edgeList=new Edge[nofEdges];
	     edgeOffsets=new int[nofNodes+1];


	     for(int i=0; i<nofNodes; i++)		// Einlesen der Knotenkoordinaten; die Daten werden wir nicht mehr nutzen
	     {						// koennten aber nuetzlich sein, wenn wir den Graph auch malen wollen
		     float x=sc.nextFloat();
		     float y=sc.nextFloat();
		     xCoords[i]=x;
		     yCoords[i]=y;
	     }
	     for(int i=0; i<nofEdges;i++)		// Einlesen der Kanten und abspeichern in der edgeList
	     {
		     int source=sc.nextInt();
		     int target=sc.nextInt();
		     int weight=sc.nextInt();

		     edgeList[i]=new Edge(source,target,weight);

	     }
	    }
	    catch(FileNotFoundException e){System.out.println("Problem beim Einlesen");}

	    // Ausgabe, was wir gerade eingelesen haben; nur zur Kontrolle 
	    //
	    System.out.println("Wir haben "+nofNodes+" Knoten und "+nofEdges+" Kanten im Graph");
//	    System.out.println("Liste der Knoten:");
//	    for(int i=0; i<nofNodes; i++)		
//	    {
//		     System.out.println(xCoords[i]+" "+yCoords[i]);
//	    }
	    System.out.println("Liste der Kanten:");
	    for(int i=0; i<nofEdges; i++)		
	    {
		     System.out.println("Kante von "+edgeList[i].src+" nach "+edgeList[i].trg+" mit Gewicht "+edgeList[i].weight);
	    }
	    
    }


    public static void computeEdgeOffsets()
    {
	    // als ERSTE AUFGABE von Ihnen zu fuellen !!!
	    // Annahme: Kanten in edgeList stehen sortiert nach
	    // Sourceknoten, d.h. zuerst kommen die Kanten mit "kleinen"
	    // Quellknoten.
	    // In dieser Methode soll das Array edgeOffsets richtig
	    // gefuellt werden, d.h.
	    // edgeOffset[v] soll fuer Knotennummer v den Index
	    // in der edgeListe enthalten, ab der die Kanten ausgehend
	    // von v stehen (Knoten sind von 0 bis nofNodes-1 nummeriert);
	    // edgeOffset[nofNodes] sollte nofEdges enthalten

    }


    public static void printAdjacentEdges(int v)
    {
	    // als ZWEITE AUFGABE von Ihnen zu fuellen !!!
	    // greifen Sie auf Ihre Graphrepraesentation zu, um die ausgehenden Kanten
	    // des uebergebenen Knotens v auszugeben
            // der Aufwand sollte proportional sein zur Anzahl der ausgegeben Kanten,
	    // in keinem Fall sollte über alle Kanten oder Knoten iteriert werden
	System.out.println("Ausgabe Adjazente Kanten von "+v);
    }

    public static void main(String[] args) {
	if (args.length!=3)
	{
		System.err.println("java Dijkstra <GraphFile> <SourceNode> <TargetNode>");
		System.exit(1);
	}

	String graphFile=args[0];
	int sourceNode=Integer.parseInt(args[1]);
	int targetNode=Integer.parseInt(args[2]);

	System.out.println("Aufruf mit Graph "+graphFile
			+" und Knoten "+sourceNode+" und "+targetNode);

	readGraph(graphFile);

	computeEdgeOffsets();


	System.out.println("Test: Ausgabe der adjazenten Kanten von "+sourceNode+" und "+targetNode);
	printAdjacentEdges(sourceNode);
	printAdjacentEdges(targetNode);
    }
}