#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" #define lc(x) ((x) << 1) #define rc(x) ((x) << 1 | 1) //#define double long double #define pii pair<int,int> #define p1(x) ((x).first) #define p2(x) ((x).second) vector<int>E[320][320]; int s[320][320]; int u[200030],v[200030],w[200300]; int n,m; bitset<210>ar[210]; int AS,NO; set<pii>ANS,NOW; vector<pii>EDT; bool ap[320][320]; inline bool chk(int i,int j,int p,int q){ return ar[q][i]||ar[j][p]; } inline void INS(int u,int v){ vector<pii>p; for(pii e:NOW) if(chk(u,v,p1(e),p2(e))) p.push_back(e); for(pii e:p){ NOW.erase(e); NO-=s[p1(e)][p2(e)]; } NOW.insert({u,v}); NO+=s[u][v]; } inline void upd(){ if(NO>AS){ AS=NO; ANS=NOW; } } mt19937 RD(time(0)); inline double rd(){ return 1.*RD()/INT_MAX; } inline void SA(){ NOW.clear(); NO=0; double T=100,dT=0.992; while(T>=1e-2){ int id=RD()%EDT.size(); if(!NOW.count(EDT[id])){ auto OD=NOW; auto od=NO; INS(p1(EDT[id]),p2(EDT[id])); if(exp(1.*(NO-od)/T)<rd()){ NOW=OD; NO=od; } } T*=dT; upd(); } } int b[400300]; signed main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); // freopen("s4.in","r",stdin); //freopen("antibody.in", "r", stdin); //freopen("antibody.out", "w", stdout); int t; cin>>n>>m>>t; //int C=clock(); for(int i=1;i<=m;i++) cin>>u[i]>>v[i]>>w[i],b[i]=u[i],b[i+m]=v[i]; sort(b+1,b+2*m+1); auto tmp=unique(b+1,b+2*m+1); for(int i=1;i<=m;i++){ u[i]=lower_bound(b+1,tmp,u[i])-b; v[i]=lower_bound(b+1,tmp,v[i])-b; } for(int i=1;i<=m;i++){ if(w[i]>0){ E[u[i]][v[i]].push_back(i); s[u[i]][v[i]]+=w[i]; ap[u[i]][v[i]]=1; } } for(int i=1;i<=n;i++) ar[i][i]=1; for(int i=1;i<=m;i++) for(int i=1;i<=m;i++) ar[u[i]]|=ar[v[i]]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(ap[i][j]) EDT.push_back({i,j}); for(int i=1;i<=100;i++) SA(); cout<<AS<<endl; vector<int>FUNC; for(pii e:ANS) for(int x:E[p1(e)][p2(e)]) FUNC.push_back(x); cout<<FUNC.size()<<endl; for(int x:FUNC) cout<<x<<" "; cout.flush(); return 0; }