#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); 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; } atcoder::scc_graph s(n); { for(int i = 0;i cnt(n,0); for(int i = 0;i can(n,-1e18); can[0] = 0; for(auto p:use){ priority_queue> que; for(int j:p) if(can[j]!=-1e18) que.push({can[j],j}); while(que.size()){ int ni = que.top().second; auto nn = que.top(); que.pop(); if(nn.first!=can[ni]) continue; for(auto id:g[ni]){ int to = v[id]; if(now[id]==1) continue; if(cnt[to]==cnt[ni]){ if(can[to]