#include"stdio.h"
#include"malloc.h"
struct task//任务的数据结构
{
	int begin;
	int last;
	struct task *next;
};
struct node//块的数据结构，代表城市。
{
	struct task *next;
};

void insert(struct node nd[],struct task *p,int k)//在对应的城市块k，添加任务p，按照结束时间递增插入。
{
	struct task *p1,*p2;
	if(nd[k].next==NULL)
		nd[k].next=p;
	else
	{
		p1=nd[k].next;
		while(p1!=NULL && (p->begin+p->last)>p1->begin+p1->last)
		{
			p2=p1;
			p1=p1->next;
		}
		if(p1==NULL)
			p2->next=p;
		else if(p1==nd[k].next)
		{
			nd[k].next=p;
			p->next=p1;
		}
		else
		{	p2->next=p;
			p->next=p1;
		}
	}
}

int main()
{
	struct node nd[20];
	struct task *p1,*ps;
	int i,j,k,bl,select,spend=0;
	int blocks,tasks,men=0;
	int finish,more;
	int road[20][20],min;
	for(i=0;i<20;i++)
		nd[i].next=NULL;
	while(1)
	{
		scanf("%d%d",&blocks,&tasks);
		if(blocks==0 && tasks==0)
			break;
		finish=1;
		more=0;
		men=0;
		for(i=0;i<20;i++)
			for(j=0;j<20;j++)
				road[i][j]=0;
		for(i=0;i<blocks;i++)
		{
			for(j=0;j<blocks;j++)
				scanf("%d",&road[i][j]);
		}
		for(i=0;i<tasks;i++)
		{
			p1=(struct task*)malloc(sizeof(struct task));
			p1->next=NULL;
			scanf("%d%d%d",&bl,&p1->begin,&p1->last);
			insert(nd,p1,bl-1);
		}
//floyd算法
		for(k=0;k<blocks;k++)
		for(i=0;i<blocks;i++)
		for(j=0;j<blocks;j++)
		{
			if(road[i][k]==-1 || road[k][j]==-1)
				continue;
			else if(road[i][j]==-1)
				road[i][j]=road[i][k]+road[k][j];
			else if(road[i][j]>road[i][k]+road[k][j])
				road[i][j]=road[i][k]+road[k][j];
		}
//接下来代码就不贴了。。。。。。。。如果上面的没问题，下面就是问题。。－_－!
       }
}