#include<stdio.h>
#include<conio.h>
#include<values.h>
#include<math.h>

struct list{
	   int u;
	   int v;
	   long c;
	   };
typedef struct list edge;
edge e[20];

int N,E,i,j,k,l,mincost,p[20],flag=0;
long min,cost[20][20],dist[20];

void read_from_file(void);
void initialize(void);
void relax(int x, int y, long z);
void output(void);
FILE *fp;

main()
  {
  clrscr();
  fp=fopen("bellman.txt","r");
  fscanf(fp,"%d%d",&N,&E);
  read_from_file();
  initialize();
  for(i=1;i<=N-1;++i)
	{
	for(j=0;j<E;++j)
		{
		relax(e[j].u,e[j].v,e[j].c);
		}
	printf("At iteration %d: ",i );
	for(int k=0; k<N;++k)
		printf("%d ",p[k]);
	printf("\n");

	}
  for(i=0;i<E;++i)
		{
		if(dist[e[i].v-1]>dist[e[i].u-1]+cost[e[i].u-1][e[i].v-1])
			 {
			 flag=1;
			 break;
			 }
		}
    output();
  }

void read_from_file(void)
  {
  for(i=0;i<N;++i)
      for(j=0;j<N;++j)
	{
	cost[i][j]=MAXINT;
	}
  min=MAXINT;
  for(i=0;i<E;++i)
	{
	fscanf(fp,"%d%d%ld",&e[i].u, &e[i].v, &e[i].c);
	cost[e[i].u-1][e[i].v-1]=e[i].c;
	if(min>e[i].c)
		{
		min=e[i].c;
		k=e[i].u-1;
		l=e[i].v-1;
		}
	}
  }

void initialize(void)
  {
  for(i=0;i<N;++i)
	{
	dist[i]=MAXINT;
	p[i]=0;
	}
  dist[k]=0;
  }

void relax(int x, int y, long z)
  {
  if (dist[y-1] > dist[x-1]+cost[x-1][y-1])
			{
			dist[y-1]= dist[x-1]+cost[x-1][y-1];
			p[y-1]=x;
			}
  }

void output(void)
  {
  int temp[20];
  if(flag==1)
	printf("Negative Weight Cycle Detected....No Shortest Path Possible");
  else
	{
	printf("Shortest Path from Source Vertex %d to all other Vertices\n\n",k+1);
	for(i=0;i<N;++i)
		{
		printf("VERTEX (%d): ",i+1);
		j=i;
		k=0;
		while(p[j]!=0)
			{
			temp[k++]=p[j];
			j=p[j]-1;
			}
		for(k=k-1;k>=0;--k)
			printf("%d-->",temp[k]);
		printf("%d (cost: %ld)\n",i+1,dist[i]);
		printf("\n");
		}
	}
  }