Djikstras && DFS  till test case 43/77 then  Djikstras dfs +DP to pass all 
Intuitionusing Dijkstras && DFS
we only reach till testcase 42/77 or sowe need dp after that
1 submistion is without dp fail for test case n=422
2 submition  is
# Intuition
using Dijkstras && DFS 
we only reach till testcase 42/77 or so

we need dp after that 
1 submistion is without dp fail for test case n=422 
2 submition  is dp pass all the test case

# Code
```java []
// 1 solution submition is tle for 422 

class store {
    int dist;
    int node;
    public store(int dist, int node) {
        this.dist = dist;
        this.node = node;
    }
}

class adj_stru {
    int u;
    int v;
    int wt;
    public adj_stru(int u, int v, int wt) {
        this.u = u;
        this.v = v;
        this.wt = wt;
    }
}

class Solution {
    public int countRestrictedPaths(int n, int[][] mat) {
        // convert the mat to adj
        ArrayList<ArrayList<adj_stru>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        int i=0;
        // Fix: Loop correctly over mat[i]
         for (int[] edge : mat) {
            int u =edge[0];
            int v = edge[1];
            int wt = edge[2];
            adj.get(u).add(new adj_stru(u, v, wt));
            adj.get(v).add(new adj_stru(v, u, wt));
        }


        // Dijkstra's algorithm
        PriorityQueue<store> queue = new PriorityQueue<>((a, b) -> a.dist - b.dist);
        int[] dist = new int[n+1];
        Arrays.fill(dist,Integer.MAX_VALUE);
        dist[n] = 0;
        int[] visit = new int[n+1];  // Fix: Declare visit array here
        Arrays.fill(visit, 0);

        queue.add(new store(0, n));  // Starting node with dist 0

        while (!queue.isEmpty()) {
            store curr = queue.poll();
            int node = curr.node;
            int distNode = curr.dist;  // Use a different variable name to avoid confusion
            for (adj_stru ele : adj.get(node)) {
                int v = ele.v;
                int wt = ele.wt;
                int cal_dist = distNode + wt;
                if (cal_dist < dist[v]) {
                    dist[v] = cal_dist;
                    queue.add(new store(cal_dist, v));
                }
            }
        }

        // DFS setup
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        ArrayList<Integer> vec = new ArrayList<>();
        

        // Start DFS from node 1
        dfs(n,1, ans, vec, adj, dist, visit);

        return ans.size();
    }

    public void dfs(int n,int node, ArrayList<ArrayList<Integer>> ans, ArrayList<Integer> vec, ArrayList<ArrayList<adj_stru>> adj, int[] dist, int[] visit) {
        visit[node] = 1;
        vec.add(node);
        if(node==n)
        {
            System.out.println(vec);
        ans.add(new ArrayList<>(vec));  // Add the current path to the answer list
        }
        else {
            for (adj_stru ele : adj.get(node)) {
            int neighborNode = ele.v;
            int neighborDist = ele.wt;

            // Check for restricted path (you might want to use dist[] here)
            if (dist[neighborNode] < dist[node]) {
                dfs(n,neighborNode, ans, vec, adj, dist, visit);
            }
        }
        }
       
        
        visit[node] = 0;  // Unmark the node after finishing the DFS on it
        vec.remove(vec.size() - 1);  // Backtrack
    }
}


################################################################################ 
// this optimaztion using dp
// 2 solution



class Solution {
    private static final int MOD = 1000000007;
    
    public int countRestrictedPaths(int n, int[][] edges) {
        // Build adjacency list using a more efficient structure
        List<int[]>[] adj = new List[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        
        // Populate adjacency list more efficiently
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adj[u].add(new int[]{v, w});
            adj[v].add(new int[]{u, w});
        }
        
        // Dijkstra with optimizations
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[n] = 0;
        
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[1], b[1]));
        pq.offer(new long[]{n, 0});
        
        while (!pq.isEmpty()) {
            long[] curr = pq.poll();
            int node = (int) curr[0];
            long d = curr[1];
            
            if (d > dist[node]) continue;
            
            for (int[] next : adj[node]) {
                int nextNode = next[0];
                int weight = next[1];
                
                if (dist[nextNode] > d + weight) {
                    dist[nextNode] = (int)(d + weight);
                    pq.offer(new long[]{nextNode, d + weight});
                }
            }
        }
        
        // Use DP array for memoization
        Integer[] memo = new Integer[n + 1];
        return dfs(1, n, adj, dist, memo);
    }
    
    private int dfs(int node, int n, List<int[]>[] adj, int[] dist, Integer[] memo) {
        if (node == n) return 1;
        if (memo[node] != null) return memo[node];
        
        long count = 0;
        for (int[] next : adj[node]) {
            int nextNode = next[0];
            if (dist[nextNode] < dist[node]) {
                count = (count + dfs(nextNode, n, adj, dist, memo)) % MOD;
            }
        }
        
        memo[node] = (int) count;
        return memo[node];
    }
}
```
['Depth-First Search', 'Graph', 'Java']