class iPair
{
    int vertex;
    int weight;
    iPair(int vertex, int weight)
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}

class Pair
{
    int node;
    int dist;
    Pair(int node, int dist)
    {
        this.node = node;
        this.dist = dist;
    }
}
class Solution {
    public int[] dijkstra(int V, int[][] edges, int src) {
        
        // Step-1 Create an adjacency list
        ArrayList<ArrayList<iPair>> adj = new ArrayList<>();
        for(int i=0; i<V; i++)
        {
            adj.add(new ArrayList<iPair>());
        }
        for(int[] edge : edges)
        {
            int u = edge[0];
            int v = edge[1];
            int w = edge[2];
            
            adj.get(u).add(new iPair(v, w));
            adj.get(v).add(new iPair(u, w));
        }
        
        // Step-2 Create a distance array
        int[] distance = new int[V];
        Arrays.fill(distance, (int)1e8);
        distance[src] = 0;
        
        // Step-3 Create a min-heap <dist, node> to store shortest distance first
        PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Integer.compare(x.dist, y.dist));
        pq.offer(new Pair(src, 0));
        
        // Step-4 Process the nodes present in Min-heap using Dijkstra
        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int currentNode = pair.node;
            int currentDist = pair.dist;
            
            for(iPair adjNode : adj.get(currentNode))
            {
                int vertex = adjNode.vertex;
                int weight = adjNode.weight;
                
                if(distance[currentNode] != (int)1e8 && distance[vertex] > currentDist + weight)
                {
                    distance[vertex] = currentDist + weight;
                    pq.offer(new Pair(vertex, distance[vertex]));
                }
            }
        }
        return distance;
    }
}