// Dijkstra's Algorithm in Java using a heap with the best S vertex for
// every T vertex.
// See CSE 2320 Notes 16.

import java.util.Scanner;

public class dijkstraHeap
{
  public static class dijkstraFails extends Exception
  {
    public dijkstraFails()
    {
      super();
    }

    public dijkstraFails(String message)
    {
      super(message);
    }
  }

  final static int oo=(1000000000);

  // Declarations

  enum st {s,t};

  static int numVertices,numEdges;

  static class edge
  {
    int tail,head,weight;
    int next;  // subscript of next edge with same tail 
  }

  static edge[] edgeTab;
  static int[] firstEdge;  // Table indicating first edge for a tail

  static void read_input_file() throws dijkstraFails
  {
    // Reads a file with a weighted, directed graph and
    // stores as unordered adjacency lists.
    int tail,head,weight,i,j,workingEdges;

    // read number of nodes and edges
    Scanner sc=new Scanner(System.in);
    numVertices=sc.nextInt();
    numEdges=sc.nextInt();

    firstEdge=new int[numVertices];
    edgeTab=new edge[numEdges];
    for (i=0;i<numEdges;i++)
      edgeTab[i]=new edge();

    // Initially, all adjacency lists are empty
    for (i=0;i<numVertices;i++)
      firstEdge[i]=(-1);

    // read edges, each with a weight
    workingEdges=0;
    for (i=0; i<numEdges; i++)
    {
      tail=sc.nextInt();
      head=sc.nextInt();
      weight=sc.nextInt();
      // Test for illegal edge.
      if (tail<0 || tail>numVertices-1 || head<0
      || head>numVertices-1 || weight<=0)
        throw new dijkstraFails("Invalid input "+tail+" "+head+" "+
          weight);
      // Save input edge and insert in adjacency list
      edgeTab[workingEdges].tail=tail;
      edgeTab[workingEdges].head=head;
      edgeTab[workingEdges].weight=weight;
      edgeTab[workingEdges].next=firstEdge[tail];
      firstEdge[tail]=workingEdges;
      workingEdges++;
    }
  }

  static void dijkstra() throws dijkstraFails,minHeap.minHeapFails
  {
    int i,j,SPedgeCount=0;
    st[] flag=new st[numVertices];
    heapEntry smallest,          // reference is returned from minHeap
      changing=new heapEntry();  // gets passed to minHeap
    int[] priority=new int[numVertices],
          bestSneighbor=new int[numVertices];

    // Vertex 0 starts in S.  Other vertices start in T.
    flag[0]=st.s;
    for (i=1;i<numVertices;i++)
      flag[i]=st.t;

    // Some T vertices might not have an edge from vertex 0.
    priority[0]=0;  // Dummy entry for vertex 0
    for (i=1;i<numVertices;i++)
      priority[i]=oo;

    // Initialize T-heap with edges from vertex 0.
    for (i=firstEdge[0];
         i!=(-1);
         i=edgeTab[i].next)
    {
      priority[edgeTab[i].head]=edgeTab[i].weight;
      bestSneighbor[edgeTab[i].head]=0;
    }

    // Constructor does BuildMinHeap
    minHeap heap=new minHeap(numVertices,priority,numVertices);
    priority=null;  // No longer needed

    // Remove dummy entry from heap
    smallest=heap.extractMin();
    if (smallest.id!=0)
      throw new dijkstraFails("Heap problem");

    // Each iteration finds another shortest-path tree edge
    for (SPedgeCount=0;SPedgeCount<numVertices-1;SPedgeCount++)
    {
      // Get minimum weight edge from S to T.
      smallest=heap.extractMin();
      if (smallest.priority==oo) // no edges remain that bridge S & T
        break;

      System.out.format("Include edge from %d to %d to give distance %d\n",
        bestSneighbor[smallest.id],smallest.id, smallest.priority);
      flag[smallest.id]=st.s;

      // Scan adjacency list looking for improvements
      for (j=firstEdge[smallest.id];
           j!=(-1);
           j=edgeTab[j].next)
        if (flag[edgeTab[j].head]==st.t
        && smallest.priority+edgeTab[j].weight
           <heap.getPriority(edgeTab[j].head))
        {
          changing.id=edgeTab[j].head;
          changing.priority=smallest.priority+edgeTab[j].weight;
          heap.changePriority(changing);
          bestSneighbor[edgeTab[j].head]=smallest.id;
        }
    }
    if (SPedgeCount<numVertices-1)
      for (i=1;i<numVertices;i++)
        if (flag[i]==st.t)
          System.out.format("Vertex %d is not reachable from vertex 0\n",i);
  }

  public static void main(String[] args)
  {
    try
    {
      read_input_file();
      dijkstra();
    }
    catch (Exception except)
    {
      System.out.format("%s\n",except.getMessage());
    }
  }

}