/*
好好的图论题啊，最短路的应用，dijkstra算法 
*/
#include 
using namespace std;
const int INF=100000;
int a[105][105],b[105],c[105],s[105],dist[105];
int n,m;
int dj(int p,int q)
{
	int i,j,r,t,k=0;
	for(i=0;i=p&&b[i]<=q)) dist[i]=a[k][i], s[i]=0; else dist[i]=INF,s[i]=0;
	dist[0]=0; s[0]=1;
	for(i=1;i=p&&b[j]<=q)
		{
			r=dist[k]+a[k][j];
			if(dist[j]>r) dist[j]=r;
		}
	}
	t=c[0];
	for(i=0;i>m>>n&&(m||n))
	{
		for(i=0;i>c[i]>>b[i]>>k;
	    for(j=0;j>p>>q;
	    a[i][p-1]=q;
	    }
	}
	r=c[0];
     for(i=b[0]-m;i<=b[0];i++)
     {
	 k=dj(i,i+m);
	 if(k