from __future__ import print_function

def printDist(dist, V):
	print("\nVertex Distance")
	for i in range(V):
		if dist[i] != float('inf') :
			print(i,"\t",int(dist[i]),end = "\t")
		else:
			print(i,"\t","INF",end="\t")
		print()

def BellmanFord(graph, V, E, src):
	mdist=[float('inf') for i in range(V)]
	mdist[src] = 0.0
	
	for i in range(V-1):
		for j in range(V):
			u = graph[j]["src"]
			v = graph[j]["dst"]
			w = graph[j]["weight"]

			if mdist[u] != float('inf') and mdist[u] + w < mdist[v]:
				mdist[v] = mdist[u] + w 
	for j in range(V):
			u = graph[j]["src"]
			v = graph[j]["dst"]
			w = graph[j]["weight"]

			if mdist[u] != float('inf') and mdist[u] + w < mdist[v]:
				print("Negative cycle found. Solution not possible.")
				return
	
	printDist(mdist, V)	

			

#MAIN
V = int(input("Enter number of vertices: "))
E = int(input("Enter number of edges: "))

graph = [dict() for j in range(E)]

for i in range(V):
	graph[i][i] = 0.0

for i in range(E):
	print("\nEdge ",i+1)
	src = int(input("Enter source:"))
	dst = int(input("Enter destination:"))
	weight = float(input("Enter weight:"))
	graph[i] = {"src": src,"dst": dst, "weight": weight}
	
gsrc = int(input("\nEnter shortest path source:"))
BellmanFord(graph, V, E, gsrc)