class Pair
{
    int node;
    long dist;
    Pair(int node, long dist)
    {
        this.node = node;
        this.dist = dist;
    }
}
class iPair
{
    int vertex;
    int weight;
    iPair(int vertex, int weight)
    {
        this.vertex = vertex;
        this.weight = weight;
    }
}

class Solution {
    /**
    Build adjacency list from the edge list.
    Use Dijkstra to find shortest distances from node 0 to all nodes
    Maintain a ways[] array:
        ways[u] = number of shortest paths to node u.
        If a new shorter path is found, update distance and ways.
        If an equal distance is found, add ways.
    Return ways[V-1] → number of shortest paths to last node. 
    */
    public int countPaths(int V, int[][] roads) {
        int MOD = 1_000_000_007;

        // 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 : roads)
        {
            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 and count ways array
        long[] distance = new long[V];
        int[] ways = new int[V];
        Arrays.fill(distance, Long.MAX_VALUE);
        // starting node is 0 so distance will be 0 and no of ways to reach from node 0-> node 0 is 1
        distance[0] = 0;
        ways[0] = 1;

        // Step-3 Define Priority queue to store the nodes according to shortest distance
        PriorityQueue<Pair> pq = new PriorityQueue<>( (x,y) -> Long.compare(x.dist, y.dist));
        pq.add(new Pair(0, 0));

        while(!pq.isEmpty())
        {
            Pair pair = pq.poll();
            int currentNode = pair.node;
            long currentDist = pair.dist;

            // stale entry
            if(currentDist > distance[currentNode]) 
                continue;

            for(iPair adjNode : adj.get(currentNode))
            {
                int vertex = adjNode.vertex;
                int weight = adjNode.weight;

                if(distance[vertex] > currentDist + weight)
                {
                    distance[vertex] = currentDist + weight;
                    pq.offer(new Pair(vertex, distance[vertex]));
                    ways[vertex] = ways[currentNode];
                }
                else if(distance[vertex] == currentDist + weight) 
                {
                    ways[vertex] = (ways[vertex]+ways[currentNode]) % MOD;
                }
            }
        }
        return ways[V-1];
    }
}