<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>

// https://leetcode.com/problems/modify-graph-edge-weights/



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

//#define MY_ASSERT       assert
#define MY_ASSERT(s)

#ifndef MY_FORCEINLINE
    #ifdef _MSC_VER
        #define MY_FORCEINLINE      __forceinline
    #else
        #define MY_FORCEINLINE      __attribute__((always_inline))
    #endif
#endif

// https://devblogs.microsoft.com/cppblog/msvc-cpp20-and-the-std-cpp20-switch/
#ifndef MY_NO_UNIQUE_ADDRESS
    #ifdef _MSC_VER
        #define MY_NO_UNIQUE_ADDRESS        [[msvc::no_unique_address]]
    #else
        #define MY_NO_UNIQUE_ADDRESS        [[no_unique_address]]
    #endif
#endif

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

namespace my {

    template<class ValT>
    MY_FORCEINLINE void swap(ValT& l, ValT& r) {
        std::swap(l, r);
    }

    template< class ValT, class IdxT = std::size_t >
    struct MyBinaryHeap_DefIndexUpdateT
    {
        using value_type = ValT;
        using value_t = value_type;
        using index_t = IdxT;

        //MY_FORCEINLINE void swap(MyBinaryHeap_DefIndexUpdateT&) {}
        MY_FORCEINLINE void onHeapElemIndexUpdate(const value_t&, index_t) {}
    };
    //
    //template<class ValT, class IdxT>
    //MY_FORCEINLINE void swap(MyBinaryHeap_DefIndexUpdateT<ValT, IdxT> & l, MyBinaryHeap_DefIndexUpdateT<ValT, IdxT> & r) {
    //    l.swap(r);
    //}
    
    // Note:
    //    When use "std::less", the max value is in the "top()".
    template< class OrigValT
            , class CtnrT = std::vector<OrigValT>
            , class CmpT = std::less<typename CtnrT::value_type>
            , class IdxUpdateT = MyBinaryHeap_DefIndexUpdateT<typename CtnrT::value_type, typename CtnrT::size_type>
        >
    class MyBinaryHeapT
    {
    public:
        using orig_value_t = OrigValT;
        using container_type = CtnrT;
        using value_compare = CmpT;
        using value_type = typename container_type::value_type;
        using size_type = typename container_type::size_type;
        using reference = typename container_type::reference;
        using const_reference = typename container_type::const_reference;

        using value_t = value_type;
        using container_t = container_type;
        using compare_t = value_compare;
        using index_update_t = IdxUpdateT;
        static_assert(std::is_same_v<typename index_update_t::value_t, value_t>);
        using index_t = typename index_update_t::index_t;

        static constexpr const size_type C_NPOS = ((size_type)-1);
        static constexpr const index_t C_INDEX_NPOS = ((index_t)-1);
        static_assert(C_NPOS == C_INDEX_NPOS);

    public:
        // get the index value (index_t) by container index value (size_type).
        static MY_FORCEINLINE constexpr index_t getIdxByCtnrIdx(size_type idxInCtnr) {
            MY_ASSERT( C_NPOS == idxInCtnr || 0 <= idxInCtnr );
            MY_ASSERT( C_NPOS == idxInCtnr || std::uint64_t(idxInCtnr) <= std::uint64_t(std::numeric_limits<index_t>::max()) );
            return static_cast<index_t>(idxInCtnr);
        }

    public:
        explicit MyBinaryHeapT(const compare_t& cmp = compare_t())
            : m_cmp(cmp)
        {
            //
        }
        MyBinaryHeapT(const compare_t& cmp
                , const index_update_t& idxUp
            )
            : m_cmp(cmp), m_idxUpdater(idxUp)
        {
            //
        }
        MyBinaryHeapT(const compare_t& cmp
                , const container_t& ctnr
                , const index_update_t& idxUp = index_update_t()
            )
            : m_ctnr(ctnr), m_cmp(cmp), m_idxUpdater(idxUp)
        {
            doInitCtnrToHeap_();
        }
        MyBinaryHeapT(const compare_t& cmp
                , container_t&& ctnr
                , const index_update_t& idxUp = index_update_t()
            )
            : m_ctnr(std::move(ctnr)), m_cmp(cmp), m_idxUpdater(idxUp)
        {
            doInitCtnrToHeap_();
        }
        MyBinaryHeapT(const MyBinaryHeapT& oth)
            : m_ctnr(oth.m_ctnr), m_cmp(oth.m_cmp), m_idxUpdater(oth.m_idxUpdater)
        {
            //
        }
        MyBinaryHeapT(MyBinaryHeapT&& oth)
            : m_ctnr(std::move(oth.m_ctnr)), m_cmp(std::move(oth.m_cmp)), m_idxUpdater(std::move(oth.m_idxUpdater))
        {
            //
        }
        ~MyBinaryHeapT() {}

        MyBinaryHeapT& operator=(const MyBinaryHeapT& oth) {
            if (this != &oth) {
                m_ctnr = oth.m_ctnr;
                m_cmp = oth.m_cmp;
                m_idxUpdater = oth.m_idxUpdater;
            }
            return *this;
        }
        MyBinaryHeapT& operator=(MyBinaryHeapT&& oth) {
            if (this != &oth) {
                m_ctnr = std::move(oth.m_ctnr);
                m_cmp = std::move(oth.m_cmp);
                m_idxUpdater = std::move(oth.m_idxUpdater);
            }
            return *this;
        }

        void swap(MyBinaryHeapT& oth) noexcept {
            if (this != &oth) {
                my::swap(m_ctnr, oth.m_ctnr);
                my::swap(m_cmp, oth.m_cmp);
                my::swap(m_idxUpdater, oth.m_idxUpdater);
            }
        }

        void reserve(size_type newCapa) { m_ctnr.reserve(newCapa); }
        size_type capacity() const { return m_ctnr.capacity(); }

        const_reference top() const { return m_ctnr.front(); }
        [[nodiscard]] bool empty() const { return m_ctnr.empty(); }
        size_type size() const { return m_ctnr.size(); }

        void push(const value_t& val) {
            const size_type iLast = m_ctnr.size();
            m_ctnr.push(val);
            doUpdateElemIndex_(iLast);
            doSiftUp_(iLast);
        }
        void push(value_t&& val) {
            const size_type iLast = m_ctnr.size();
            m_ctnr.push(std::move(val));
            doUpdateElemIndex_(iLast);
            doSiftUp_(iLast);
        }

        template<class... Args>
        void emplace(Args&&... args) {
            const size_type iLast = m_ctnr.size();
            m_ctnr.emplace_back( std::forward<Args>(args)... );
            doUpdateElemIndex_(iLast);
            doSiftUp_(iLast);
        }

        void pop() {
            MY_ASSERT(!m_ctnr.empty());
            const size_type iLast = m_ctnr.size() - 1;
            if (iLast != 0) {
                doSwapElem_(0, iLast);
            }
            doRemoveUpdateElemIndex_(m_ctnr.back());
            m_ctnr.pop_back();
            if (1 < iLast) {
                doSiftDown_(0);
            }
        }

        void erase(size_type i) {
            MY_ASSERT(0 <= i && i < m_ctnr.size());
            const size_type iLast = m_ctnr.size() - 1;
            if (iLast != i) {
                doSwapElem_(i, iLast);
                doRemoveUpdateElemIndex_(m_ctnr.back());
                m_ctnr.pop_back();
                onElemUpdated(i);
            } else {
                doRemoveUpdateElemIndex_(m_ctnr.back());
                m_ctnr.pop_back();
            }
        }

        const_reference getElem(size_type i) const {
            MY_ASSERT(0 <= i && i < m_ctnr.size());
            return m_ctnr[i];
        }
        // Note:
        //    Be careful:
        //       after one call of "getElemRef()" and change its value, an IMMEDIATELY
        //       call of "onElemUpdated()/siftUp()/siftDown()" should be followed !!!
        reference getElemRef(size_type i) {
            MY_ASSERT(0 <= i && i < m_ctnr.size());
            return m_ctnr[i];
        }
        inline void onElemUpdated(size_type i) {
            doSiftUp_(i);
            doSiftDown_(i);
        }
        inline void siftUp(size_type i) {
            doSiftUp_(i);
        }
        inline void siftDown(size_type i) {
            doSiftDown_(i);
        }

        void updateElem(size_type i, const value_t& newVal) {
            MY_ASSERT(0 <= i && i < m_ctnr.size());
            m_ctnr[i] = newVal;
            onElemUpdated(i);
        }
        void updateElem(size_type i, value_t&& newVal) {
            MY_ASSERT(0 <= i && i < m_ctnr.size());
            m_ctnr[i] = std::move(newVal);
            onElemUpdated(i);
        }

        void clear() {
            for (const auto& elem: m_ctnr) {
                doRemoveUpdateElemIndex_(elem);
            }
            m_ctnr.clear();
        }
        void clearWithoutUpdateIndex() {
            m_ctnr.clear();
        }

    private:
        static constexpr size_type parentIndex_(size_type i) {
            MY_ASSERT(0 < i);
            return ((i - 1) >> 1);
        }
        static constexpr size_type leftChildIndex_(size_type i) { return (i << 1) + 1; }
        static constexpr size_type rightChildIndex_(size_type i) { return (i << 1) + 2; }

        inline void doSwapElem_(size_type i, size_type j) {
            MY_ASSERT(i != j);
            my::swap(m_ctnr[i], m_ctnr[j]);
            m_idxUpdater.onHeapElemIndexUpdate( m_ctnr[i], getIdxByCtnrIdx(i) );
            m_idxUpdater.onHeapElemIndexUpdate( m_ctnr[j], getIdxByCtnrIdx(j) );
        }
        MY_FORCEINLINE void doUpdateElemIndex_(size_type i) {
            m_idxUpdater.onHeapElemIndexUpdate( m_ctnr[i], getIdxByCtnrIdx(i) );
        }
        MY_FORCEINLINE void doRemoveUpdateElemIndex_(const value_t& elem) {
            m_idxUpdater.onHeapElemIndexUpdate(elem, C_INDEX_NPOS);
        }

        void doSiftDown_(size_type i) {
            MY_ASSERT(0 <= i && i < m_ctnr.size());
            size_type iChild = leftChildIndex_(i);
            while (iChild < m_ctnr.size()) {
                size_type iSel = ( m_cmp(m_ctnr[i], m_ctnr[iChild]) ? iChild : i );
                ++iChild; // right child
                if (iChild < m_ctnr.size() && m_cmp(m_ctnr[iSel], m_ctnr[iChild]))
                    iSel = iChild;
                if (iSel != i) {
                    doSwapElem_(i, iSel);
                    i = iSel;
                    iChild = leftChildIndex_(i);
                } else {
                    break;
                }
            }
        }
        void doSiftUp_(size_type i) {
            MY_ASSERT(0 <= i && i < m_ctnr.size());
            while (0 < i) {
                size_type iParent = parentIndex_(i);
                if (m_cmp(m_ctnr[iParent], m_ctnr[i])) {
                    doSwapElem_(i, iParent);
                    i = iParent;
                } else {
                    break;
                }
            }
        }

        void doInitCtnrToHeap_() {
            for (size_type i = 0; i < m_ctnr.size(); ++i) {
                doUpdateElemIndex_(i);
            }
            for (size_type i = (m_ctnr.size() >> 1) - 1; C_NPOS != i; --i) {
                doSiftDown_(i);
            }
        }

    private:
        container_t m_ctnr;
        MY_NO_UNIQUE_ADDRESS compare_t m_cmp;
        MY_NO_UNIQUE_ADDRESS index_update_t m_idxUpdater;
    };
    //
    template<class OrigValT, class CtnrT, class CmpT, class IdxUpdateT>
    MY_FORCEINLINE void swap(MyBinaryHeapT<OrigValT, CtnrT, CmpT, IdxUpdateT> & l, MyBinaryHeapT<OrigValT, CtnrT, CmpT, IdxUpdateT> & r) noexcept {
        l.swap(r);
    }

} // namespace my

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



static const auto s_initialize = [] { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return nullptr; }();

class Solution {
public:
    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
        return modifiedGraphEdges_v1(n, edges, source, destination, target);
    }

    static constexpr const int C_INT_MAX = std::numeric_limits<int>::max();
    static constexpr const int C_UPDATE_VAL_MAX = 2000000000;


private:
    // method 1.
    //    Editorial, Approach 2: Dijkstra's Algorithm with Min-Heap.
    //
    // O( m * (n + m*log(n)) ); O( n + m ).
    //
    struct v1_data_t
    {
        int dist;
        int idx;

        explicit v1_data_t(int aDist = -1, int aIdx = -1): dist(aDist), idx(aIdx) {}
    };
    struct v1_heap_cmp_t
    {
        inline bool operator()(const v1_data_t& l, const v1_data_t& r) const {
            return l.dist > r.dist;
        }
    };
    struct v1_heap_index_update_t
    {
        using value_t = v1_data_t;
        using index_t = int;

        std::vector<int> * m_pvHpIdx;

        explicit v1_heap_index_update_t(std::vector<int> * pvHpIdx = nullptr): m_pvHpIdx(pvHpIdx) {}

        MY_FORCEINLINE void onHeapElemIndexUpdate(const value_t& rcVal, index_t hpIdx) {
            (*m_pvHpIdx)[rcVal.idx] = hpIdx;
        }
    };
    using v1_heap_t = my::MyBinaryHeapT< v1_data_t, std::vector<v1_data_t>, v1_heap_cmp_t, v1_heap_index_update_t >;
    //
    vector<vector<int>> modifiedGraphEdges_v1(const int n, vector<vector<int>>& edges, const int iSrc, const int iDest, const int target) {
        const int m = static_cast<int>(edges.size());
        std::vector< std::vector< std::pair<int, int> > > vvEdges( n );
        std::vector< std::pair<int, int> > vIdxOfEdge;
        vIdxOfEdge.reserve( m );
        for (const auto& edge: edges) {
            int ia = edge[0];
            int ib = edge[1];
            if (ib < ia)
                std::swap(ia, ib);
            const int iw = edge[2];
            vIdxOfEdge.emplace_back( static_cast<int>(vvEdges[ia].size()), static_cast<int>(vvEdges[ib].size()) );
            vvEdges[ia].emplace_back( ib, iw );
            vvEdges[ib].emplace_back( ia, iw );
        }
        //
        std::vector<int> vHpIdx;
        v1_heap_t hp( v1_heap_cmp_t(), (v1_heap_index_update_t(&vHpIdx)) );
        hp.reserve(n);
        std::function< int() > tDijkstra;
        tDijkstra = [=, &tDijkstra, &vvEdges, &vHpIdx, &hp] () -> int {
            hp.clear();
            vHpIdx.assign( n, -2 );
            hp.emplace( 0, iSrc );
            while (!hp.empty()) {
                const auto tDat = hp.top();
                if (iDest == tDat.idx) {
                    return tDat.dist;
                }
                hp.pop();
                for (const auto [ni, nw]: vvEdges[tDat.idx]) {
                    if (-1 != nw) {
                        const int tmpDist = tDat.dist + nw;
                        const auto hpIdx = vHpIdx[ni];
                        if (-1 < hpIdx) {
                            auto& rElem = hp.getElemRef(hpIdx);
                            if (tmpDist < rElem.dist) {
                                rElem.dist = tmpDist;
                                hp.siftUp(hpIdx);
                            }
                        } else if (-2 == hpIdx) {
                            hp.emplace( tmpDist, ni );
                        }
                    }
                }
            }
            return -1;
        };
        //
        std::vector< std::vector<int> > vvRes;
        int tmpDist = tDijkstra();
        //std::cout << " tmpDist: " << tmpDist << ".\n";
        if (-1 != tmpDist) {
            if (tmpDist < target) {
                return vvRes;
            } else if (tmpDist == target) {
                vvRes.reserve(m);
                for (int i = 0; i < m; ++i) {
                    vvRes.emplace_back( std::vector<int>{ edges[i][0], edges[i][1], (-1 != edges[i][2] ? edges[i][2] : C_UPDATE_VAL_MAX) } );
                }
                return vvRes;
            }
        }
        //
        for (int i = 0; i < m; ++i) {
            if (-1 == edges[i][2]) {
                edges[i][2] = 1;
                int ia = edges[i][0];
                int ib = edges[i][1];
                if (ib < ia)
                    std::swap(ia, ib);
                vvEdges[ia][ vIdxOfEdge[i].first ].second = 1;
                vvEdges[ib][ vIdxOfEdge[i].second ].second = 1;
                tmpDist = tDijkstra();
                //std::cout << " tmpDist: " << tmpDist << ".\n";
                if (-1 != tmpDist && tmpDist <= target) {
                    edges[i][2] += (target - tmpDist);
                    vvRes.reserve(m);
                    for (int i = 0; i < m; ++i) {
                        vvRes.emplace_back( std::vector<int>{ edges[i][0], edges[i][1], (-1 != edges[i][2] ? edges[i][2] : C_UPDATE_VAL_MAX) } );
                    }
                    return vvRes;
                }
            }
        }
        return vvRes;
    }

};

233462