static class Main{
    class Edge{
        int from;
        int to;
        int dis;
        public Edge(int from, int to, int dis){
            this.from = from;
            this.to = to;
            this.dis = dis;
        }
    }

    public static void main(String[] args) throws Exception{

        // 정점의 개수는 N이라고 하고, 간선의 개수를 M개 있다고 할 때
        int[] distance = new int[N+1];
        Edge[] edgeList = new Edge [M+1];

        for(int i=1; i<=N; i++) distance[i] = Integer.MAX_VALUE;
        for(int i=1; i<=N; i++) edgeList[i]= new Edge("간선에 대한 정보 저장");

        int start = 1; // 일단 start를 1번정점이라고 가정함
        distance[start] = 0; // 자기 자신으로 가는 길이이니까 0으로 초기화해준다.

        // 사용할 수 있는 간선의 수를 N-1개까지 사용해보면서
        // 할 수있는 최단거리를 구하는 것이다.
        for(int i=1; i<=N-1; i++){
            // i는 간선을 사용하는 횟수이다. 즉 i가 1이면 간선을 한번만 사용해서 갈 수 있는 구간을 찾는다.
            // i가 1... n이면 간선을 3번 사용해서 갈 수있는 값이
            // 이전까지의 값(1,2 .... n-1번 사용)보다 작으면 최신화 시켜준다.

            // start가 1이고 distance[1] = 0 이기 때문에 당연히 1부터 시작하는
            // 다른 모든 정점으로의 최솟값으로 구해질 수밖에 없다.
            for(int j=1; j<=M; j++){
                Edge nowEdge = edgeList[j];
                if(distance[nowEdge.from] != Integer.MAX_VALUE){
                    if(distance[nowEdge.to] > distance[nowEdge.from] + nowEdge.distance){
                        distance[nowEdge.to] = distance[nowEdge.from] + nowEdge.distance;
                    }
                }
            }
        }

        boolean findNegativeCycle = false;
        // 각 간선을 확인하며 지금까지 구했던 값들보다(N-1개의 간선을 사용하는 방법)
        // 더 작은 값이 발생한다면 음의 싸이클이 존재한다는 뜻이다.
        for(int j=1; j<=M; j++){
            Edge nowEdge = edgeList[j];
            if(distance[nowEdge.from] != INF){
                if(distance[nowEdge.to] > distance[nowEdge.from] + nowEdge.distance){
                    findNegativeCycle = true;
                    break;
                }
            }
        }
        // 음의 싸이클이 발생하면 distance배열의 값들이 의미가 없어진다.
        // 만약 findNegativeCycle이 false라면  distance배열에는 각 값들중 최단거리가 저장되어있다.
    }
}