// Memoryless version of Dijkstra's algorithm
// See CSE 2320, Notes 14.
// This is coded with everything in main() because it is very slow.
#include <stdio.h>
#include <stdlib.h>

typedef enum {s,t} stType;

main()
{
int numVertices,numEdges;
int i,j,smallestWeight,smallestEdgeNumber,SPedgeCount;
stType *flag;  // flag[i] indicates which set vertex i is in.
int *vertex1,*vertex2,*weight;  // Input tables
int *dist;  // Distance from vertex 0 for vertices in S

scanf("%d %d",&numVertices,&numEdges);
flag=(stType*) malloc(numVertices*sizeof(stType));

// Three parallel arrays instead of array of structs
vertex1=(int*) malloc(numEdges*sizeof(int));
vertex2=(int*) malloc(numEdges*sizeof(int));
weight=(int*) malloc(numEdges*sizeof(int));
dist=malloc(numVertices*sizeof(int));
if (!flag || !vertex1 || !vertex2 || !weight || !dist)
{
  printf("malloc() failed %d\n",__LINE__);
  exit(0);
}

// Get input directed edges.  Store in simple tables.
for (i=0;i<numEdges;i++)
{
  scanf("%d %d %d",&vertex1[i],&vertex2[i],&weight[i]);
  if (vertex1[i]<0 || vertex1[i]>numVertices-1 || vertex2[i]<0 || 
     vertex2[i]>numVertices-1 || weight[i]<=0)
  {
    printf("Bad input %d\n",__LINE__);
    exit(0);
  }
}

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

for (SPedgeCount=0;SPedgeCount<numVertices-1;SPedgeCount++)
{
  // Simple redundant scan of all edges to find an S to T edge
  // to complete shortest path over all vertices in T.
  smallestWeight=999999999;
  for (i=0;i<numEdges;i++)
    if (flag[vertex1[i]]==s && flag[vertex2[i]]==t
    && dist[vertex1[i]]+weight[i]<smallestWeight)
      {
        smallestWeight=dist[vertex1[i]]+weight[i];
        smallestEdgeNumber=i;
      }
  if (smallestWeight==999999999)
    break;

  dist[vertex2[smallestEdgeNumber]]=smallestWeight;
  printf("Include edge from %d to %d to give distance %d\n",
    vertex1[smallestEdgeNumber],vertex2[smallestEdgeNumber],
    smallestWeight);
  // Put vertex in S.
  flag[vertex2[smallestEdgeNumber]]=s;
}
if (SPedgeCount<numVertices-1)
  for (i=1;i<numVertices;i++)
    if (flag[i]==t)
      printf("Vertex %d is not reachable from vertex 0\n",i);
free(flag);
free(vertex1);
free(vertex2);
free(weight);
free(dist);
}