(UVA) Wormholes - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=499


import java.io.*;
import java.util.*;

class Main {
    public static void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            int numNodes = sc.nextInt();
            int numEdges = sc.nextInt();
           
            ArrayList<Edge> edges = new ArrayList<>();
            for (int j = 0; j < numEdges; j++) {
                int n1 = sc.nextInt();
                int n2 = sc.nextInt();
                int cost = sc.nextInt();
               
                edges.add(new Edge(n1, n2, cost));
            }
           
            int[] costs = new int[numNodes];
            for (int j = 0; j < numNodes; j++) {
                costs[j] = 1047483647;
            }
           
            costs[0] = 0;
            for (int j = 0; j < numNodes; j++) {
                for (int k = 0; k < edges.size(); k++) {
                    int n1 = edges.get(k).node1;
                    int n2 = edges.get(k).node2;
                    int cost = edges.get(k).cost;       
               
                    if (costs[n2] > cost+costs[n1]) {
                        costs[n2] = cost+costs[n1];
                    }
                }
            }
           
            boolean change = false;
            for (int j = 0; j < numNodes && !change; j++) {
                for (int k = 0; k < edges.size(); k++) {
                    int n1 = edges.get(k).node1;
                    int n2 = edges.get(k).node2;
                    int cost = edges.get(k).cost;       
               
                    if (costs[n2] > cost+costs[n1]) {
                        costs[n2] = cost+costs[n1];
                        change = true;
                        break;
                    }
                }
            }
           
            if (change) {
                System.out.println("possible");
            }
            else {
                System.out.println("not possible");
            }
        }
                               
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}

class Edge {
    int node1;
    int node2;
    int cost;
   
    public Edge(int n1, int n2, int c) {
        node1 = n1;
        node2 = n2;
        cost = c;
    }
}