12.2.1

http://cybern.ru/algoritm-forda-bellmana-realizaciya-na-java.html
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.io.PrintWriter;


/**
 * Created by Сергей on 27.05.2016.
 */
public class Solution321 {
    public static void main(String Args[]) {
        class Edge {
            int from;
            int to;
            int weight;

            public Edge(int u, int v, int w) {
                this.from = u;
                this.to = v;
                this.weight = w;
            }
        }
        int INF = Integer.MAX_VALUE / 2;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//колличество вершин
        int m = sc.nextInt();//колличество ребер
            Edge[] edges = new Edge[m];




        int W[][] = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                W[i][j] = INF;
            }
        }
        int i1, j1, w1;

            for (int i = 0; i < m; i++) {
                // Считываем начальную и конечную вершину
                // i-ой дуги, а также её вес
                int from = sc.nextInt();
                int to = sc.nextInt();
                int weight = sc.nextInt();
                // Так как нами используется 0-индексация,
                // то уменьшим индексы вершин на единицу
                from--;
                to--;

                // Кладем считанную дугу в массив дуг
                edges[i] = new Edge(from, to, weight);
            }

        // Создаем массив, i-ый элемент которого
        // будет хранить текущее расстояние от 1-ой
        // (или 0-ой в нашем случае 0-индексации)
        // до i-ой вершины графа
        int[] distance = new int[n];

        // До начала работы алгоритма все расстояния,
        // кроме 0-го, равны бесконечности (условной)
        Arrays.fill(distance, INF);
        distance[0] = 0;

        // В соответствии с алгоритмом будем
        // обновлять массив расстояний
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < m; j++) {
                int from = edges[j].from;
                int to = edges[j].to;
                int weight = edges[j].weight;

                // Ясно, что если вершина from на
                // текущем шаге работы алгоритма
                // находится бесконечно далеко от
                // 0-ой, то она не изменит ответ
                if (distance[from] == INF) {
                    continue;
                }

                // В противном случае обновим
                // расстояние до вершины to,
                // это называют релаксацией
                distance[to] = Math.min(distance[to],
                        distance[from] + weight);
            }
        }
        // Выводим расстояние от 0-ой вершины
        // до каждой отличной от нее
        for (int i = 0; i < n; i++) {
            if (distance[i] == INF) {
                System.out.println("NO");
            } else {
                System.out.println(distance[i]);
            }
        }

    }
}