<p>You are given an <strong>undirected weighted</strong> <strong>connected</strong> graph containing <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code>, and an integer array <code>edges</code> where <code>edges[i] = [a<sub>i</sub>, b<sub>i</sub>, w<sub>i</sub>]</code> indicates that there is an edge between nodes <code>a<sub>i</sub></code> and <code>b<sub>i</sub></code> with weight <code>w<sub>i</sub></code>.</p>

<p>Some edges have a weight of <code>-1</code> (<code>w<sub>i</sub> = -1</code>), while others have a <strong>positive</strong> weight (<code>w<sub>i</sub> &gt; 0</code>).</p>

<p>Your task is to modify <strong>all edges</strong> with a weight of <code>-1</code> by assigning them <strong>positive integer values </strong>in the range <code>[1, 2 * 10<sup>9</sup>]</code> so that the <strong>shortest distance</strong> between the nodes <code>source</code> and <code>destination</code> becomes equal to an integer <code>target</code>. If there are <strong>multiple</strong> <strong>modifications</strong> that make the shortest distance between <code>source</code> and <code>destination</code> equal to <code>target</code>, any of them will be considered correct.</p>

<p>Return <em>an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from </em><code>source</code><em> to </em><code>destination</code><em> equal to </em><code>target</code><em>, or an <strong>empty array</strong> if it&#39;s impossible.</em></p>

<p><strong>Note:</strong> You are not allowed to modify the weights of edges with initial positive weights.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/18/graph.png" style="width: 300px; height: 300px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5
<strong>Output:</strong> [[4,1,1],[2,0,1],[0,3,3],[4,3,1]]
<strong>Explanation:</strong> The graph above shows a possible modification to the edges, making the distance from 0 to 1 equal to 5.
</pre>

<p><strong class="example">Example 2:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/18/graph-2.png" style="width: 300px; height: 300px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6
<strong>Output:</strong> []
<strong>Explanation:</strong> The graph above contains the initial edges. It is not possible to make the distance from 0 to 2 equal to 6 by modifying the edge with weight -1. So, an empty array is returned.
</pre>

<p><strong class="example">Example 3:</strong></p>

<p><strong class="example"><img alt="" src="https://assets.leetcode.com/uploads/2023/04/19/graph-3.png" style="width: 300px; height: 300px;" /></strong></p>

<pre>
<strong>Input:</strong> n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6
<strong>Output:</strong> [[1,0,4],[1,2,3],[2,3,5],[0,3,1]]
<strong>Explanation:</strong> The graph above shows a modified graph having the shortest distance from 0 to 2 as 6.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code><font face="monospace">1 &lt;= edges.length &lt;= n * (n - 1) / 2</font></code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= a<sub>i</sub>, b<sub>i&nbsp;</sub>&lt;&nbsp;n</code></li>
	<li><code><font face="monospace">w<sub>i</sub>&nbsp;= -1&nbsp;</font></code>or <code><font face="monospace">1 &lt;= w<sub>i&nbsp;</sub>&lt;= 10<sup><span style="font-size: 10.8333px;">7</span></sup></font></code></li>
	<li><code>a<sub>i&nbsp;</sub>!=&nbsp;b<sub>i</sub></code></li>
	<li><code>0 &lt;= source, destination &lt; n</code></li>
	<li><code>source != destination</code></li>
	<li><code><font face="monospace">1 &lt;= target &lt;= 10<sup>9</sup></font></code></li>
	<li>The graph is connected, and there are no self-loops or repeated edges</li>
</ul>

///////////////////////////////////////////////////

using grid_t = vector<vector<int>>;
using edge_t = vector<vector<int>>;

using ull = unsigned long long int;
using lint = long long int;

// dijkstra and heap with priority updates
namespace my {
template <class Key, class Pri> class Heap {
public:
  virtual void push(Key, Pri) = 0;
  virtual pair<Key, Pri> pop(void) = 0;

  virtual bool is_empty() = 0;
};

template <class Key, class Pri> class HeapUpdates : public Heap<Key, Pri> {
public:
  virtual bool update_key(Key, Pri) = 0;
};

template <class Pri> class MinBinaryHeap : public HeapUpdates<size_t, Pri> {
public:
  MinBinaryHeap(size_t n) {
    arr.reserve(n);
    mp.resize(n);

    for (int i = 0; i < n; ++i) {
      mp[i] = -1;
    }
  }

  void push(size_t k, Pri p) override {
    size_t indx = arr.size();
    arr.emplace_back(p, k);

    mp[k] = indx;
    this->up(indx);
  }

  // don't pop when empty
  pair<size_t, Pri> pop(void) override {
    pair<Pri, size_t> top = arr[0];

    this->swap_arr(0, arr.size() - 1);
    mp[top.second] = -1;
    arr.resize(arr.size() - 1);

    this->down(0);

    return make_pair(top.second, top.first);
  }

  // always updates
  bool update_key(size_t k, Pri p) override {
    int i = mp[k];
    if (i != -1) {
      Pri before = arr[i].first;
      arr[i].first = p;

      if (p < before) {
        up(i);
      } else if (p > before) {
        down(i);
      }

      return true;
    }

    return false;
  }

  bool is_empty() override { return arr.empty(); }

  Pri priority_of(size_t k) {
    int i = mp[k];
    if (i != -1) {
      return arr[i].first;
    }
    return -1;
  }

private:
  vector<pair<Pri, size_t>> arr; // <priority, key>
  vector<int> mp;                // key => arr index; -1 when empty

  void up(size_t i) {
    if (i == 0) {
      return;
    }

    auto p = this->parent_index(i);
    if (!this->ok(p, i)) {
      this->swap_arr(p, i);
      this->up(p);
    }
  }

  void down(size_t i) {
    auto j = this->small_child_index(i);
    if (j == -1) {
      return;
    }

    if (!this->ok(i, j)) {
      this->swap_arr(i, j);
      this->down(j);
    }
  }

  // parent, child
  bool ok(size_t i, size_t j) { return arr[i].first < arr[j].first; }

  size_t small_child_index(size_t i) {
    int j1 = 2 * i + 1, j2 = 2 * i + 2;

    if (j1 >= arr.size()) {
      return -1;
    }
    if (j2 >= arr.size()) {
      return j1;
    }

    return this->ok(j1, j2) ? j1 : j2;
  }

  size_t parent_index(size_t i) { return (i - 1) / 2; }

  void swap_arr(size_t i, size_t j) {
    auto ki = arr[i].second, kj = arr[j].second;

    auto tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;

    mp[ki] = j;
    mp[kj] = i;
  }
};

using weight_t = long long int;

const weight_t inf = 10101010101010LL;

class MinIntBinaryHeap final : public MinBinaryHeap<weight_t> {
public:
  MinIntBinaryHeap(size_t n) : MinBinaryHeap(n) {}
};

struct weight_edge {
  weight_edge() {}
  weight_edge(weight_t w, size_t x, size_t y, size_t i)
      : w(w), x(x), y(y), i(i) {
  } // initializing for convenience of type narrowing!

  weight_t w;
  size_t x;
  size_t y;
  size_t i;
};

class Dij {
public:
  vector<optional<weight_t>> costs; // works as key=>priority for heap, but
                                    // the heap itself is independent

  // n vertices, directed edges with weights
  Dij(int n, vector<weight_edge> &edges) : heap(n), costs(n), next_weight(n) {
    for (auto item : edges) {
      int x = item.x, y = item.y, i = item.i;
      weight_t w = item.w;

      next_weight[x].emplace_back(y, w, i);
      next_weight[y].emplace_back(x, w, i); // makes it undirected
    }
  }

  // dijkstra's algo starting from index s
  void run(size_t s) {
    for (auto &item : costs) {
      item = nullopt;
    }
    heap.push(s, 0); // initial cost of s

    for (; !heap.is_empty();) {
      auto [cur, cost] = heap.pop();

      costs[cur] = cost;
      for (auto [nxt, w, _] : next_weight[cur]) {
        weight_t next_cost = cost + w;

        if (next_cost >= inf) {
          continue;
        }

        if (costs[nxt] && *costs[nxt] <= next_cost) {
          continue;
        }

        if (!costs[nxt]) {
          heap.push(nxt, next_cost);
        } else if (*costs[nxt] > next_cost) {
          heap.update_key(nxt, next_cost);
        }

        costs[nxt] = next_cost;
      }
    }

    return;
  }

  vector<vector<tuple<size_t, weight_t, size_t>>> next_weight;

private:
  MinIntBinaryHeap heap;
};
} // namespace my

class Solution {
public:
  vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>> &edges,
                                         int source, int destination,
                                         int target) {
    vector<my::weight_edge> edge1, edgeinf;
    edge1.reserve(edges.size());
    edgeinf.reserve(edges.size());
    for (int i = 0; i < edges.size(); ++i) {
      auto item = edges[i];
      edge1.push_back(
          my::weight_edge(item[2] == -1 ? 1 : item[2], item[0], item[1], i));
      edgeinf.push_back(my::weight_edge(item[2] == -1 ? my::inf : item[2],
                                        item[0], item[1], i));
    }

    my::Dij left(n, edge1), right(n, edgeinf);
    left.run(source);
    right.run(destination);

    if (*left.costs[destination] > target ||
        (right.costs[source] && *right.costs[source] < target)) {
      return {};
    }

    if (!walk_left(source, destination, left.costs, right.costs,
                   left.next_weight, edges, 0LL, (long long int)target)) {
      return {};
    }

    for (auto &item : edges) {
      if (item[2] == -1) {
        item[2] = target + 10;
      }
    }

    return edges;
  }

  bool walk_left(int s, int t, vector<optional<my::weight_t>> left,
                 vector<optional<my::weight_t>> right,
                 vector<vector<tuple<size_t, my::weight_t, size_t>>> adj,
                 edge_t &edges, my::weight_t total, long long int target) {
    if (s == t) {
      return total == target;
    }

    for (auto item : adj[s]) {
      auto [v, w, i] = item;
      if (*left[v] == *left[s] + w) {
        if (edges[i][2] == -1 && right[v]) {
          if (long long int d = target - total - *right[v]; d > 0) {
            edges[i][2] = d;
            return true;
          } else {
            if (walk_left(v, t, left, right, adj, edges, total + 1, target)) {
              edges[i][2] = 1;
              return true;
            }
          }
        } else {
          if (walk_left(v, t, left, right, adj, edges, total + w, target)) {
            edges[i][2] = w;
            return true;
          }
        }
      }
    }

    return false;
  }
};

483532