private static void shortestPath(Edge[] edges, int n) {
		// previous node of our shortest path
		int[] predecessor = new int[n];
		// sum of c along the shortest path
		int[] distance = new int[n];

		// initialisation
		for (int i = 0; i < n; i++) {
			predecessor[i] = -1;
			distance[i] = Integer.MAX_VALUE;
		}

		// init start node
		predecessor[0] = 0;
		distance[0] = 0;

		for (int i = 0; i < n; i++) {
			for (Edge edge : edges) {
				if (predecessor[edge.u] != -1) {

					int newDist = edge.c + distance[edge.u];
					if (newDist < distance[edge.v]) {
						distance[edge.v] = newDist;
						predecessor[edge.v] = edge.u;
					}
				}
			}
		}

		// check for negative-weight cycles
		for (Edge edge : edges) {
			if (distance[edge.u] + edge.c < distance[edge.v]) {
				System.out.println("NEGATIVE-CYCLE");
				return;
			}
		}

		boolean isFirst = true;
		for (int dist : distance) {
			if (!isFirst) {
				System.out.print(" ");
			}
			System.out.print(dist);
			isFirst = false;
		}
		System.out.print("\n");

	}