#include<bits/stdc++.h> #include<bits/extc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; using namespace __gnu_pbds; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; ll pw[70]; struct nd { int x,y,w,op;bool fl; }d[205]; bool operator<(nd a,nd b){ if(a.w!=b.w)return a.w<b.w; return a.fl>b.fl; } gp_hash_table<ll,int>mp[205],mp2[205]; ll gc(int a,int b){return (a/pw[b])%10;} ll trans(ll S,int x,int y){ ll res=0; x=gc(S,x),y=gc(S,y);if(x>y)swap(x,y); up(i,0,n-1){ ll k=gc(S,i); if(k<y)res=res+k*pw[i]; else if(k==y)res=res+x*pw[i]; else res=res+(k-1)*pw[i]; } return res; } inline void chkmax(int &x,int y){x=max(x,y);} void slv(){ n=read(),m=read();int s=0; pw[0]=1;up(i,1,n)pw[i]=pw[i-1]*10; up(i,1,m){ int x=read(),y=read(),a=read(),b=read(); ++s;d[s].x=x,d[s].y=y,d[s].w=a,d[s].op=1,d[s].fl=a<=b; ++s;d[s].x=x,d[s].y=y,d[s].w=b,d[s].op=2,d[s].fl=a>b; }m=s; sort(d+1,d+m+1); ll x=0;up(i,1,n)x=x+pw[i-1]*i;mp[0][x]=0; up(i,1,m){ up(j,0,m)mp2[j].clear(); up(j,0,m)for(auto it:mp[j]){ if(gc(it.p1,d[i].x-1)==gc(it.p1,d[i].y-1)){ if(d[i].fl) up(p,j,j+1)chkmax(mp2[p][it.p1],it.p2); else chkmax(mp2[j][it.p1],it.p2); continue; } ll nx=trans(it.p1,d[i].x-1,d[i].y-1); if(d[i].fl){ chkmax(mp2[j+(d[i].op==1)][nx],it.p2+d[i].w); chkmax(mp2[j+(d[i].op==2)][it.p1],it.p2); }else chkmax(mp2[j][nx],it.p2+d[i].w); } up(j,0,m)mp[j].swap(mp2[j]),mp2[j].clear(); //cout<<"Test "<<d[i].x<<" "<<d[i].y<<" "<<d[i].w<<" "<<d[i].op<<endl; //up(j,0,i)for(auto it:mp[j]) // cout<<i<<" "<<j<<" "<<it.p1<<" "<<it.p2<<endl; }s=0;up(i,1,n)s=s*10+1; up(i,0,m/2)printf("%d\n",mp[i][s]); } int main(){ //freopen("mst.in","r",stdin),freopen("mst.out","w",stdout); slv(); return 0; }