import java.io.*;

public class Main {
    final static int INFINITY = 9999;
    final static String PATH = "D:\\My_content\\My_Desktop\\BellmanFord\\src\\";

    public static void main(String[] args) throws IOException {
        PrintWriter pw = new PrintWriter(new File(PATH + "output.txt"));

        int countOfFiles = (int) (50 + Math.random() *50);
        for (int i = 0; i < countOfFiles; i++) {
            int vert = makeInput(PATH + "inputs\\input" + i + ".txt");
            int[][] edges = readInput(PATH + "inputs\\input" + i + ".txt", vert);

            long timeNow = System.nanoTime() / 1000;
            int iteration = bellmanFord(edges, 1);
            long timeAfter = System.nanoTime()/1000 - timeNow;
            pw.println((new File(PATH + "inputs\\input" + i + ".txt").length()/1024 ) + "\t" +
                    iteration + "\t" +
                    timeAfter);
        }
        pw.close();
    }

    public static int bellmanFord(int[][] edges, int source) {
        int n = edges.length;
        int dist[] = new int[n];
        int iter = 0;

        for (int i = 0; i < n; i++) {
            dist[i] = INFINITY;
        }
        dist[source] = 0;
        for (int k = 0; k < n - 1; k++) {
            boolean any = false;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    iter++;
                    if (edges[i][j] != INFINITY) {
                        if ((dist[j] > dist[i] + edges[i][j]) && edges[i][j] != 0) {
                            dist[j] = dist[i] + edges[i][j];
                            any = true;
                        }
                    }
                }
            }
            if (!any) break;
        }
        return iter;
    }

    public static int makeInput(String path) throws FileNotFoundException {
        int countOfEdges = (int) (100 + Math.random() * 1000);
        int countOfVertex = (int) (20 + Math.random() * 100);
        PrintWriter pw = new PrintWriter(new File(path));
        for (int i = 0; i < countOfEdges; i++) {
            pw.print((int) (Math.random() * countOfVertex));
            pw.print(" ");
            pw.print((int) (Math.random() * countOfVertex));
            pw.print(" ");
            pw.print((int) (1 + Math.random() * 99));
            pw.println();
        }

        pw.close();
        return countOfVertex;
    }

    public static int[][] readInput(String path, int countOfVertex) throws IOException {
        FileReader fileReader = new FileReader(new File(path));
        BufferedReader br = new BufferedReader(fileReader);
        String line = null;
        int[][] edges = new int[countOfVertex][countOfVertex];
        while ((line = br.readLine()) != null) {
            String[] lines = line.split(" ");
            if (lines.length == 3) {
                edges[Integer.parseInt(lines[0])][Integer.parseInt(lines[1])] = Integer.parseInt(lines[2]);
            }
        }
        return edges;
    }
}