Link 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);
	}
}