#include #include #include using namespace std; using ll = long long; #include #include int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll n,m,q; cin>>n>>m>>q; vector> g(n); vector u(m),v(m),w(m); atcoder::scc_graph s(n); for(int i = 0;i>u[i]>>v[i]>>w[i]; u[i]--;v[i]--; g[u[i]].push_back(i); s.add_edge(u[i],v[i]); } vector now(m,0); auto use = s.scc(); vector cnt(n,0); for(int i = 0;i>j; j--; now[j] ^= 1; } vector can(n,-1e18); can[0] = 0; for(auto p:use){ priority_queue> que; // vector que; for(int j:p) if(can[j]!=-1e18) que.push({can[j],j}); while(que.size()){ // cout<