CSES - Shared codeLink to this code:
https://cses.fi/paste/0a487e7ca8b42fe92c6a35/
import java.util.Scanner;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.PriorityQueue;
class practice{
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
ArrayList<ArrayList<p>> graph = new ArrayList<>();
for(int i=0;i<n;i++)
graph.add(new ArrayList<>());
for(int i=0;i<m;i++)
graph.get(in.nextInt()-1).add(new p(in.nextInt()-1,in.nextInt()));
long[] dist = new long[n];
Arrays.fill(dist,Long.MAX_VALUE);
dist[0]=0;
boolean[] vis = new boolean[n];
PriorityQueue<p> q = new PriorityQueue<>();
q.add(new p(0,0));
p cur;
// n--;
while(!q.isEmpty() && n>0) {
cur = q.poll();
if(vis[cur.a]) continue;
vis[cur.a] = true;
n--;
for(p edge : graph.get(cur.a)) {
if(vis[edge.a]) continue;
long newDist = dist[cur.a] + edge.b;
if(dist[edge.a] > newDist) {
dist[edge.a] = newDist;
q.add(new p(edge.a,newDist));
}
}
}
for(long x : dist)
System.out.print(x + " ");
}
}
class p implements Comparable<p>{
int a;
long b;
p(int a,long b){
this.a=a;
this.b=b;
}
public int compareTo(p x) {
return (int)(this.b - x.b);
}
}