BellmanFord.java

import java.util.*;
public class Main {
 public static void main(String[] args) {
 Scanner scn = new Scanner(System.in);
 int n = scn.nextInt();
 int m = scn.nextInt();
 int[][] matrix = new int[m][3];
 for (int i = 0; i
 < m; i++) {
 int u = scn.nextInt();
 int v = scn.nextInt();
 int w = scn.nextInt();
 matrix[i][0] = u - 1;
 matrix[i][1] = v - 1;
 matrix[i][2] = w;
 }
 int[] path = new int[n];
 Arrays.fill(path, Integer.MAX_VALUE);
 path[0] = 0;
 scn.close();
 for (int i = 0; i < n - 1; i++) {
 for (int j = 0; j
 < m; j++) {
 int u = matrix[j][0];
 int v = matrix[j][1];
 int w = matrix[j][2];
 if (path[u] == Integer.MAX_VALUE) {
 continue;
 }
 if (path[u] + w < path[v]) {
 path[v] = path[u] + w;
 }
 }
 }
 for (int i = 1; i < path.length; i++) {
 if (path[i] == Integer.MAX_VALUE)
 {
 System.out.print( "1000000000" + " " );
 }
 else {
 System.out.print(path[i] + " " );
 }
 }
 }
}