#include <stdio.h>
#include <stdlib.h>
int iO,iP,iM;
int tab[300][5];
int tab2[300];
int gdzie[300];
int pom[301][301];
int min(int a,int b)
{
    if(a==0)return b;
    if(b==0) return a;
    if(a<b)return a;
    else return b;
}


void f()
{
    int znal=0;
    int i,j,k,z;


for(i=1;i<=iP;i++)
     for(k=0;k<iP;k++){
        if(tab[k][0]==1&&tab2[k]==0)
        {
            if(i==1){
                    tab2[k]=1;
            pom[tab[k][1]][tab[k][3]]=
            min(tab[k][2],pom[tab[k][1]][tab[k][3]-1]);
            }
            if(tab[k][1]==tab[k+1][1]&&tab[k][0]==tab[k+1][0])
            {
if(tab[k][3]+1!=tab[k+1][3])
{int a;
    for(a=tab[k][3]+1;a<tab[k+1][3];a++)
    pom[tab[k][1]][a]=pom[tab[k][1]][a-1];
}

            }
            if((tab[k+1][1]!=tab[k][1]&&k+1<iP
               &&tab[k][0]==tab[k+1][0])||(k==iP-1)||(tab[k][0]!=tab[k+1][0])&&k+1<iP)
            {
                int d;
                for(d=tab[k][3]+1;d<=iM;d++)
                    pom[tab[k][1]][d]=pom[tab[k][1]][d-1];
            }
            znal=1;
        }
        if(tab2[k]==0&&pom[tab[k][0]][iM]!=0)
        {
            tab2[k]=1;
            int nr_osady=tab[k][0];
            int gdzie_idziemy=tab[k][1];
            int cena=tab[k][3];
            int czas=tab[k][2];
            int a=0;
        while(pom[nr_osady][a]==0){a++;}

        for(a;a<=iM;a++){
        if(a+tab[k][3]>iM){
       }
        else{


             pom[gdzie_idziemy][a+tab[k][3]]=min(pom[gdzie_idziemy][a-1],pom[nr_osady][a]+czas);
        }


        }
     }

     }

     if(znal==0){
        printf("NIE\n");
        return;
     }
 }

main()
{
int i,j;
FILE *fp;
fp=fopen("in.txt", "r");
int z;

//FILE *out=fopen("out.txt","w");
fscanf(fp,"%d %d %d",&iO,&iP,&iM);
for(i=0;i<iP;i++)
{
for(j=0;j<5;j++){
        if(j==4)
tab[i][j]=i+1;
else
fscanf (fp, "%d", &tab[i][j]);


}
}


for(i=0;i<iP;i++)
{
for(j=0;j<5;j++)
printf("%d ",tab[i][j]);
printf("\n");
}
f();
for(z=0;z<=iM;z++)

    {
        for(j=0;j<=iO;j++)
        printf("%d ",pom[j][z]);
        printf("\n");
    }

}