#include #include #include #include #define LL long long #define Re register int using namespace std; const int N=103,M=503; int n,m,o,x,y,z,K,ans,pan[N],head[N],dp[N][1024+3];queueQ; struct QAQ{int w,to,next;}a[M<<1]; inline void add(Re x,Re y,Re z){a[++o].w=z,a[o].to=y,a[o].next=head[x],head[x]=o;} inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline void SPFA(Re s){ while(!Q.empty()){ Re x=Q.front();Q.pop();pan[x]=0; for(Re i=head[x],to;i;i=a[i].next) if(dp[x][s]+a[i].w