Number of restricted paths from first to last node

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  pub fn count_restricted_paths(n: i32, edges: Vec<Vec<i32>>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = n as usize;
    let mut adj = vec![vec![]; n + 1];
    for e in &edges {
      let (u, v, w) = (e[0] as usize, e[1] as usize, e[2] as i64);
      adj[u].push((v, w));
      adj[v].push((u, w));
    }

    // Dijkstra from node n
    let mut dist = vec![i64::MAX; n + 1];
    dist[n] = 0;
    let mut heap = BinaryHeap::new();
    heap.push(Reverse((0i64, n)));
    while let Some(Reverse((d, u))) = heap.pop() {
      if d > dist[u] { continue; }
      for &(v, w) in &adj[u] {
        if dist[u] + w < dist[v] {
          dist[v] = dist[u] + w;
          heap.push(Reverse((dist[v], v)));
        }
      }
    }

    // Sort nodes by increasing distance from n (node n first, dist=0)
    // When processing u, we add dp[v] for neighbors v with dist[v] < dist[u].
    // Since v has smaller dist, v appears earlier in order and dp[v] is already set.
    // So process in DECREASING distance order so that when we reach u, all v with
    // dist[v] < dist[u] have already been computed.
    // dist[n]=0 is smallest, so process it last... wait:
    // We need dp[u] = sum of dp[v] for v with dist[v] < dist[u].
    // Process from largest dist to smallest: when processing u,
    // all v neighbors with smaller dist haven't been computed yet!  
    // Actually we need to process in INCREASING dist order (from n outward):
    // dp[n]=1; for u with dist[u] > dist[v], dp[u] += dp[v] (v closer to n).
    // So process u in increasing dist order? No:
    // When processing u in increasing dist, v (smaller dist) was processed first -> dp[v] set. Correct.
    let mut order: Vec<usize> = (1..=n).collect();
    order.sort_by(|&a, &b| dist[a].cmp(&dist[b])); // increasing dist

    let mut dp = vec![0i64; n + 1];
    dp[n] = 1; // node n has dist=0, processed first
    for &u in &order {
      // Copy dp[u] computed so far
      let dp_u = dp[u];
      for &(v, _) in &adj[u] {
        if dist[u] < dist[v] {
          // u is closer to n than v; restricted path goes v -> u -> ... -> n
          dp[v] = (dp[v] + dp_u) % MOD;
        }
      }
    }
    dp[1] as i32
  }
}