Java, Dijikstra + DFS with memo
\nLong[] cache;\n    public int countRestrictedPaths(int n, int[][] edges) {\n        cache=new Long[n+1];\n        Map<Integer,Map<Integer,Integer>> graph=new 
```\nLong[] cache;\n    public int countRestrictedPaths(int n, int[][] edges) {\n        cache=new Long[n+1];\n        Map<Integer,Map<Integer,Integer>> graph=new HashMap<>();\n        for(int[] edge:edges){\n            graph.computeIfAbsent(edge[0],k->new HashMap<>()).put(edge[1],edge[2]);\n            graph.computeIfAbsent(edge[1],k->new HashMap<>()).put(edge[0],edge[2]);\n        }\n        int[] dis=new int[n+1];\n        Arrays.fill(dis,Integer.MAX_VALUE);\n        dis[n]=0;\n        PriorityQueue<int[]> pq=new PriorityQueue<>((a,b)->(a[1]-b[1]));\n        pq.add(new int[]{n,0});\n        while(!pq.isEmpty()){\n            int[] cur=pq.poll();\n            Map<Integer,Integer> children=graph.get(cur[0]);\n            if(children==null) continue;\n            for(int child:children.keySet()){\n                if(dis[child]>cur[1]+children.get(child))\n                {\n                    dis[child]=cur[1]+children.get(child);\n                    pq.add(new int[]{child,dis[child]});\n                }\n            }\n        }\n\t\t//**since there are many duplicate states, BFS can\'t pass OJ**\n        // long res=0,mod=(long)1e9+7;\n        // Queue<int[]> queue=new LinkedList<>();\n        // queue.add(new int[]{n,0});\n        // while(!queue.isEmpty()){\n        //     int[] cur=queue.poll();\n        //     if(cur[0]==1) {\n        //         res=(res+1)%mod;\n        //         continue;\n        //     }\n        //     Map<Integer,Integer> children=graph.get(cur[0]);\n        //     if(children==null) continue;\n        //     for(int child:children.keySet()){\n        //         if(dis[child]>cur[1])\n        //             queue.add(new int[]{child,dis[child]});\n        //     }\n        // }\n        return (int)dfs(n,graph,0,dis);\n        \n    }\n    \n    public long dfs(int cur,Map<Integer,Map<Integer,Integer>> graph,int dis,int[] distance){\n        if(cur==1) return 1;\n        if(cache[cur]!=null) return cache[cur];\n        Map<Integer,Integer> children=graph.get(cur);\n        long res=0,mod=(long)1e9+7;\n        if(children!=null) {\n           for(int child:children.keySet()){\n                if(distance[child]>dis)\n                    res=(res+dfs(child,graph,distance[child],distance))%mod;\n           } \n        }\n        cache[cur]=res;\n        return res;\n    }\n```
[]