//LYLAKIOI #include <iostream> #include <cstdio> #include <math.h> #include <algorithm> #include <istream> #include <string> #include <queue> #include <deque> #include <random> #include <stack> #include <set> #include <string.h> #include <map> #include <unordered_map> #include <sstream> #include <bitset> #include <fstream> #include <climits> #include <time.h> #include <cassert> using namespace std; //#include "atcoder/all" // using namespace atcoder; #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #define endl "\n" #define int long long #define double long double #define pii pair<int, int> #define p1(x) (x).first #define p2(x) (x).second #define lc(x) ((x) << 1) #define rc(x) ((x) << 1 | 1) #define i128 __int128_t vector<pii>g[400300]; vector<int>t[400300]; int d[400300]; int u[400300],v[400300],w[400300]; int n,m; inline bool bfs(int S,int T){ memset(d,-1,sizeof(d)); d[S]=0; queue<int>q; q.push(S); while(!q.empty()){ int u=q.front(); q.pop(); for(auto e:g[u]){ int v=p1(e),w=p2(e); if(w&&d[v]==-1){ d[v]=d[u]+1; q.push(v); } } } return d[T]!=-1; } int nw[400300]; inline int dfs(int u,int fl,int T){ if(!fl||u==T)return fl; int res=0; int k=g[u].size(); for(;nw[u]<k;nw[u]++){ if(!fl)break; int i=nw[u]; int v=p1(g[u][i]),w=p2(g[u][i]); if(d[v]==d[u]+1){ int tmp=dfs(v,min(w,fl),T); res+=tmp; p2(g[v][t[u][i]])+=tmp; p2(g[u][i])-=tmp; fl-=tmp; } } return res; } const int INF=1e13; inline int dinic(int S,int T){ int RES=0; while(bfs(S,T)){ memset(nw,0,sizeof(nw)); RES+=dfs(S,INF,T); } return RES; } vector<int>G[400300]; inline void add(int u,int v,int w){ G[u].push_back(v); t[u].push_back(g[v].size()); t[v].push_back(g[u].size()); g[u].push_back({v,w}); g[v].push_back({u,0}); } bool ch[400300]; inline void bfs(int n){ queue<int>q; for(int i=0;i<n;i++) if(ch[i]) q.push(i); while(!q.empty()){ int u=q.front(); q.pop(); for(auto v:G[u]){ // cout<<u<<" "<<v<<endl; if(ch[v]==0){ ch[v]=1; q.push(v); } } } } inline int MWCSG(int n,vector<int>A,vector<pii>E){ int S=n,T=n+1; int SM=0; for(auto e:E) add(p1(e),p2(e),INF); for(int i=0;i<n;i++){ if(A[i]<=0) add(i,T,-A[i]); else if(A[i]>0)add(S,i,A[i]),SM+=A[i]; } // for(int i=0;i<=n+1;i++) // for(pii e:g[i]) // cout<<i<<" "<<p1(e)<<" "<<p2(e)<<endl; // cout<<endl; int r=dinic(S,T); // for(int i=0;i<=n+1;i++) // for(pii e:g[i]){ // cout<<i<<" "<<p1(e)<<" "<<p2(e)<<endl; // } for(pii e:g[S]) if(p2(e)) ch[p1(e)]=1; int x=0; // for(int i=0;i<n;i++) // cout<<ch[i]<<" "; // cout<<endl; bfs(n); x=0; for(int i=0;i<n;i++){ x+=ch[i]*A[i]; } cout<<x<<endl; return SM-r; } inline void slv(){ int tr=0; cin>>n>>m>>tr; vector<pii>E; vector<int>A(n+m); for(int i=0;i<m;i++){ cin>>u[i]>>v[i]>>w[i]; u[i]--,v[i]--; E.push_back({u[i],v[i]}); E.push_back({u[i],n+i}); E.push_back({n+i,v[i]}); w[i]=max(0ll,w[i]); A[v[i]]+=w[i]; A[n+i]=-w[i]; } cout<<MWCSG(n+m,A,E)<<endl; vector<int>ANS; // for(int i=0;i<n+m;i++) // cout<<ch[i]<<" "; // cout<<endl; int r=0; for(int i=0;i<m;i++) if(w[i]>0&&!ch[u[i]]&&ch[v[i]]) ANS.push_back(i+1),r+=w[i]; // cout<<r<<endl; cout<<ANS.size()<<endl; for(int x:ANS)cout<<x<<" "; cout<<endl; } inline void MT(){ int t; cin>>t; while(t--)slv(); } signed main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // freopen("/Users/noip2019/Downloads/antibody/ex_antibody2.in","r",stdin); // MT(); slv(); cout.flush(); return 0; } /* 13 0 1 0 0 0 0 1 0 1 1 0 1 0 */