| 35 | } |
| 36 | // main function |
| 37 | public static void main(String[] args) throws Exception { |
| 38 | BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); |
| 39 | |
| 40 | int vtces = Integer.parseInt(br.readLine()); |
| 41 | ArrayList<Edge>[] graph = new ArrayList[vtces]; |
| 42 | for (int i = 0; i < vtces; i++) { |
| 43 | graph[i] = new ArrayList<>(); |
| 44 | } |
| 45 | |
| 46 | int edges = Integer.parseInt(br.readLine()); |
| 47 | for (int i = 0; i < edges; i++) { |
| 48 | String[] parts = br.readLine().split(" "); |
| 49 | int v1 = Integer.parseInt(parts[0]); |
| 50 | int v2 = Integer.parseInt(parts[1]); |
| 51 | int wt = Integer.parseInt(parts[2]); |
| 52 | graph[v1].add(new Edge(v1, v2, wt)); |
| 53 | graph[v2].add(new Edge(v2, v1, wt)); |
| 54 | } |
| 55 | |
| 56 | int src = Integer.parseInt(br.readLine()); |
| 57 | // this function prints shortest path to each city (in terms of kms) from the source city along |
| 58 | // with the total distance on path from source to destinations. |
| 59 | shortPath(graph,src) ; |
| 60 | |
| 61 | } |
| 62 | |
| 63 | public static void shortPath(ArrayList<Edge>[] graph,int src){ |
| 64 | boolean []flag=new boolean[graph.length] ; |