// Memoryless version of Prim's algorithm
// See CSE 2320, Notes 15.
// This is coded with everything in main() because it is very slow, O(VE).
// Also, the edges are stored in input order.

#include <stdio.h>
#include <stdlib.h>

// Simulated infinity value
#define oo (1000000000)

typedef enum {s,t} stType;

main()
{
int numVertices,numEdges;
int i,j,MSTedgeCount=0,MSTweight=0,smallestWeight,smallestEdgeNumber;
stType *flag;  // flag[i] indicates which set vertex i is in.
int *vertex1,*vertex2,*weight;  // Input tables

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));
if (!flag || !vertex1 || !vertex2 || !weight)
{
  printf("malloc() failed %d\n",__LINE__);
  exit(0);
}

// Get input undirected 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;
for (i=1;i<numVertices;i++)
  flag[i]=t;

for (MSTedgeCount=0;MSTedgeCount<numVertices-1;MSTedgeCount++)
{
  // Simple redundant scan of all edges to find least weight edge
  // to complete a path from S side to T side.
  smallestWeight=oo;
  for (i=0;i<numEdges;i++)
    if (flag[vertex1[i]]!=flag[vertex2[i]] // vertices in opposite sides
    && weight[i]<smallestWeight)
    {
      smallestWeight=weight[i];
      smallestEdgeNumber=i;
    }
  if (smallestWeight==oo)
    break;

  MSTweight+=smallestWeight;
  printf("Include edge from %d to %d of weight %d\n",
    vertex1[smallestEdgeNumber],vertex2[smallestEdgeNumber],
    smallestWeight);
  // Put both vertices in S, even though one of them is already there.
  flag[vertex1[smallestEdgeNumber]]=flag[vertex2[smallestEdgeNumber]]=s;
}

if (MSTedgeCount<numVertices-1)
  printf("Stopped after collecting %d edges of weight %d\n",
    MSTedgeCount,MSTweight);
else
  printf("Found MST with weight %d\n",MSTweight);
free(flag);
free(vertex1);
free(vertex2);
free(weight);
}