/*

*/

# include <bits/stdc++.h>

const int N=405,INF=0x3f3f3f3f;

inline int read(void){
	int res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}
typedef long long ll;

ll dis[3][N][N]; // 012 dis

int n,m;

inline void floyd(ll d[N][N]){
	for(int k=1;k<=n;++k){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				d[i][j]=std::min(d[i][j],d[i][k]+d[k][j]);
			}
		}
	}
	return;
}

int main(void){
	n=read(),m=read(); memset(dis,INF,sizeof(dis));
	for(int i=1;i<=n;++i) dis[0][i][i]=dis[1][i][i]=dis[2][i][i]=0;
	for(int i=1;i<=m;++i){
		int u=read(),v=read(),w=read(),l=read();
		for(int x=0;x<=l;++x) dis[x][u][v]=std::min(dis[x][u][v],1ll*w);
	}
	floyd(dis[0]),floyd(dis[1]);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			dis[2][i][j]=std::min(dis[2][i][j],2ll*dis[1][i][j]+dis[0][j][i]);
		}
	}
	floyd(dis[2]);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			printf("%lld ",dis[2][i][j]<=1e18?dis[2][i][j]:-1);
		}
		puts("");
	}

	return 0;
}