//朴素迪杰斯特拉算法
class CN2Dis
 {
 public:
 CN2Dis(int iSize) :m_iSize(iSize), DIS(m_vDis), PRE(m_vPre)
 {}
 void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
 {
 m_vDis.assign(m_iSize, -1);
 m_vPre.assign(m_iSize, -1);
 vector vDo(m_iSize);//点是否已处理
 auto AddNode = [&](int iNode)
 {
 //const int iPreNode = m_vPre[iNode];
 long long llPreDis = m_vDis[iNode];vDo[iNode] = true;
  for (const auto& it : vNeiB[iNode])
  {
    if (vDo[it.first])
    {
      continue;
    }

    if ((-1 == m_vDis[it.first]) || (it.second + llPreDis < m_vDis[it.first]))
    {
      m_vDis[it.first] = it.second + llPreDis;
      m_vPre[it.first] = iNode;
    }
  }

  long long llMinDis = LLONG_MAX;
  int iMinIndex = -1;
  for (int i = 0; i < m_vDis.size(); i++)
  {
    if (vDo[i])
    {
      continue;
    }
    if (-1 == m_vDis[i])
    {
      continue;
    }
    if (m_vDis[i] < llMinDis)
    {
      iMinIndex = i;
      llMinDis = m_vDis[i];
    }
  }
  return (LLONG_MAX == llMinDis) ? -1 : iMinIndex;
};

int next = start;
m_vDis[start] = 0;
while (-1 != (next = AddNode(next)));}
 void Cal(int start, const vector<vector>& mat)
 {
 m_vDis.assign(m_iSize, LLONG_MAX);
 m_vPre.assign(m_iSize, -1);
 vector vDo(m_iSize);//点是否已处理
 auto AddNode = [&](int iNode)
 {
 long long llPreDis = m_vDis[iNode];
 vDo[iNode] = true;
 for (int i = 0; i < m_iSize; i++)
 {
 if (vDo[i])
 {
 continue;
 }
 const long long llCurDis = mat[iNode][i];
 if (llCurDis <= 0)
 {
 continue;
 }
 m_vDis[i] = min(m_vDis[i], m_vDis[iNode] + llCurDis);
 }
 long long llMinDis = LLONG_MAX;
 int iMinIndex = -1;
 for (int i = 0; i < m_iSize; i++)
 {
 if (vDo[i])
 {
 continue;
 }
 if (m_vDis[i] < llMinDis)
 {
 iMinIndex = i;
 llMinDis = m_vDis[i];
 }
 }
 if (LLONG_MAX == llMinDis)
 {
 return -1;
 }m_vPre[iMinIndex] = iNode;
  return iMinIndex;
};

int next = start;
m_vDis[start] = 0;
while (-1 != (next = AddNode(next)));}
 const vector& DIS;
 const vector& PRE;
 private:
 const int m_iSize;
 vector m_vDis;//各点到起点的最短距离
 vector m_vPre;//最短路径的前一点
 };class CNeiBo3
 {
 public:
 CNeiBo3(int n, vector<vector>& edges, bool bDirect, int iBase = 0)
 {
 m_vNeiB.resize(n);
 AddEdges(edges, bDirect, iBase);
 }
 CNeiBo3(int n)
 {
 m_vNeiB.resize(n);
 }
 void AddEdges(vector<vector>& edges, bool bDirect, int iBase = 0)
 {
 for (const auto& v : edges)
 {
 m_vNeiB[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
 if (!bDirect)
 {
 m_vNeiB[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
 }
 }
 }
 vector<vector<std::pair<int,int>>> m_vNeiB;
 };

class Solution {
public:
  vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
    m_n = n;
    m_src = source;
    m_dest = destination;
    for (const auto& v : edges)
    {
      if (-1 == v[2])
      {
        m_vLess0Edge.emplace_back(v);
      }
      else
      {
        m_vMore0Edge.emplace_back(v);
      }
    }
    long long left = 0, r = (long long)(1000 * 1000 * 1000-1)* m_vLess0Edge.size()+1;
    while (r - left > 1)
    {
      const auto mid = left + (r - left) / 2;
      const long long ll = Do(mid);
      if ( ll == target )
      {
        m_vLess0Edge.insert(m_vLess0Edge.end(), m_vMore0Edge.begin(), m_vMore0Edge.end());
        return m_vLess0Edge;
      }
      else if (ll > target)
      {
        r = mid;
      }
      else
      {
        left = mid;
      }
    }
    const long long ll = Do(left);
    if (target == ll)
    {
      m_vLess0Edge.insert(m_vLess0Edge.end(), m_vMore0Edge.begin(), m_vMore0Edge.end());
      return m_vLess0Edge;
    }
    return {};
  }
  long long Do(long long llAdd)
  {
    CalLess0Edge(llAdd);
    CNeiBo3 neiBo(m_n);
    neiBo.AddEdges(m_vMore0Edge,false);
    neiBo.AddEdges(m_vLess0Edge, false);
    CN2Dis dis(m_n);
    dis.Cal(m_src, neiBo.m_vNeiB);
    return dis.DIS[m_dest];
  }
  void CalLess0Edge(long long llAdd)
  {
    for (auto& v : m_vLess0Edge)
    {
      const int curAdd = (int)min(llAdd, (long long)1000 * 1000 * 1000 - 1);
      v[2] = 1 + curAdd;
      llAdd -= curAdd;
    }
  }
  int m_n;
  int m_src;
  int m_dest;
  vector<vector<int>> m_vMore0Edge,m_vLess0Edge;
};